22972번 - 테러 스페셜 저지

문제

먼 옛날, 용산구 선린마을에는 수직선 위에 집 $N$채가 자리하고 있었다.

왼쪽으로부터 순서대로 각 집의 위치는 $P_1, \cdots, P_N$이었고, 가장 왼쪽에 있는 집의 위치 $P_1$은 0ドル$이었다.

어느 날 정휘는 선린마을에 있는 서로 다른 두 집 사이의 거리를 모두 측정했다.

즉, 모든 1ドル \le i < j \le N$에 대해, $i$번째 집과 $j$번째 집의 거리인 $P_j - P_i$를 측정했다.

예를 들어, 4개의 집의 위치가 각각 0,ドル 1, 3, 4$에 있었다면, 정휘는 집들 사이의 거리인 1ドル-0=1,ドル 3ドル-0=3,ドル 3ドル-1=2,ドル 4ドル-0=4,ドル 4ドル-1=3,ドル 4ドル-3=1$을 각각 측정했다.

그리고 정휘는 결과들을 정렬해서 6개의 수 1,ドル 1, 2, 3, 3, 4$를 기록해두었다.

하지만 오늘, 여러분이 천하제일 코딩대회를 치는 사이, 극단 원리주의 민초파 김준원이 선린마을의 집들을 모두 파괴했다.

여러분은 정휘가 기록해놓은 $N(N-1)/2$개의 수를 이용해 선린마을의 집을 복원해야 한다.

입력

첫째 줄에 선린마을에 있던 집의 개수 $N$이 주어진다.

둘째 줄에 정휘가 측정한 $N(N-1)/2$ 개의 거리를 오름차순으로 정렬한 결과 $D_1, D_2, \cdots , D_{N(N-1)/2}$가 공백으로 구분되어 주어진다.

출력

입력을 토대로 복원한 선린마을의 집들의 위치를 나타내는 $N$개의 정수 $P_1, P_2, \cdots , P_N$을 공백으로 구분해 출력하라.

여러분이 복원한 집들의 위치가,

• $P_1 = 0$
• $P_1 < P_2 < \cdots < P_N$
• 모든 1ドル \le i < j \le N$에 대해 $P_j - P_i$의 값들을 모은 $N(N-1)/2$개의 수들을 오름차순으로 정렬하면, 입력으로 주어진 $D_1, \cdots , D_{N(N-1)/2}$과 같다.

를 모두 만족하면 정답으로 인정된다.

제한

• 2ドル \leq N \leq 20$
• 1ドル \le D_i \le 1,000円,000円,000円$ (1ドル \le i \le N(N-1)/2$)
• $D_i \le D_{i+1}$ (1ドル \le i < N(N-1)/2$). 즉, $D_1, \cdots, D_{N(N-1)/2}$는 오름차순으로 정렬되어 있다.
• 조건을 만족하도록 집들의 위치를 복원할 수 있다.

힌트