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}$는 오름차순으로 정렬되어 있다.
• 조건을 만족하도록 집들의 위치를 복원할 수 있다.