Reconstruction Problem (APCS 2025-01 Advanced)

For an integer array \(a_1,a_2,\ldots,a_n\) of length \(n\) with \(a_1=0\), define its distance multiset as

It contains the absolute difference between every pair of elements, for a total of \(\frac{n(n-1)}{2}\) values.

You are given the contents of \(\Delta(a)\). It is guaranteed that at least one strictly increasing array beginning with \(0\) produces this distance multiset. Among all possible arrays, output the lexicographically smallest and the lexicographically largest arrays.

For example, let \(n=3\) and \(\Delta=(3,4,7)\). The largest distance, \(7\), must be the distance between the minimum value \(0\) and the maximum value, so the maximum array value is \(7\). The remaining point can be either \(3\) or \(4\), producing \((0,3,7)\) and \((0,4,7)\).

Input

The first line contains one positive integer \(n\).

The second line contains \(\frac{n(n-1)}{2}\) positive integers describing the distance multiset \(\Delta\). When \(n=1\), the second line is empty.

Constraints

• \(1\le n\le 25\)
• Every value in \(\Delta\) is between \(1\) and \(100\), inclusive
• At least one valid array is guaranteed to exist

Output

On the first line, output the lexicographically smallest array that produces \(\Delta\).

On the second line, output the lexicographically largest array that produces \(\Delta\).

Each line must contain \(n\) integers separated by single spaces.

Scoring

The time limit for every test case is 1 second. The score is the sum of the independently passed test cases.

Sample Input 1

3
3 4 7

Sample Output 1

0 3 7
0 4 7

Sample Explanation 1

The distance multiset \((3,4,7)\) can be produced by \((0,3,7)\) or \((0,4,7)\). These are respectively the lexicographically smallest and largest answers.

Sample Input 2

5
1 2 3 3 5 5 6 8 10 11

Sample Output 2

0 1 3 6 11
0 5 8 10 11

Source

2025 January APCS Programming Implementation, Problem 3: ZeroJudge q183, Reconstruction Problem.