시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1024 MB 0 0 0 0.000%

문제

Let X = (x1, x2, . . . , xn) be an integer sequence whose elements are distinct. The spectrum of X, denoted by spec(X), is the multiset {|xi−xj| : 1 ≤ i < j ≤ n}. Notice that a multiset counts multiplicity but ignores order. For example, {1, 1, 2} and {2, 1, 1} are the same, but {1, 1, 2} and {1, 2} are different in multisets. For simplicity, we assume that sequence X is in the ascending order and x1 = 0. For example, suppose X = (0, 1, 4, 5). Then spec(X) = {1, 1, 3, 4, 4, 5}. Given X, it is easy to compute spec(X). However, given spec(X), it is not an easy task to recover X from spec(X). In fact, it is possible that spec(X) = spec(Y ) for two different sequences X and Y . For example, spec(0, 7, 20) = {7, 13, 20} = spec(0, 13, 20). Your job is to recover all possible X’s such that spec(X) is equal to the specified spectrum in the input.

입력

The first line in a test case gives you the number n, which is the size of the integer sequence X. The second line gives you the spectrum of X, which is a multiset and the numbers d1, . . . , dn(n−1)/2 are listed in nondescending order with a single space as the delimiter between two consecutive numbers.

출력

First, output the total number of possible X’s (i.e. the number of solutions) in a line. Then dump all possible X’s in the lexicographic order (i.e. the dictionary order), one X per line. Let Y = (y1, . . . , yn) and Z = (z1, . . . , zn) be two such solutions. Then Y should precede Z if and only if there exists some index k where 1 ≤ k ≤ n such that yk < zk and yj = zj for all 1 ≤ j < k. For example, the sequence Y = (0, 7, 20) should precede Z = (0, 13, 20) in the lexicographic order because y2 < z2 (i.e. 7 < 13) and y1 = z1. For each X, print its elements in ascending order with a single space between two consecutive numbers.

제한

  • 2 ≤ n ≤ 62.
  • 0 < d1 ≤ d2 ≤ · · · ≤ dn(n−1)/2.
  • Your output should satisfy: 0 ≤ xi ≤ 999 for 1 ≤ i ≤ n and x1 = 0.
  • xi < xj for 1 ≤ i < j ≤ n.

예제 입력 1

4
2 2 2 4 4 6

예제 출력 1

1
0 2 4 6

예제 입력 2

5
3 3 6 9 9 12 12 15 18 21

예제 출력 2

2
0 3 12 15 21
0 6 9 18 21

예제 입력 3

4
5 6 7 8 9 10

예제 출력 3

0