배낭 채우기

휴가를 갈 때 가장 어려운 일 중 하나는 짐의 무게가 최대 허용치를 넘지 않도록 하는 것이다. 기내 수하물 포장 협회의 회장인 당신은 바로 이 문제에 직면해 있다. 당신은 친구와 함께 즐거운 휴가를 떠나려 하지만, 지금은 배낭을 싸느라 대부분의 시간을 짜증 속에 보내고 있다. 이 과정을 최적화하기 위해 당신과 친구는 각자 더 나은 포장 방법을 찾기로 했다.

얼마 후 당신은 엄청난 돌파구를 마련했다! 어떻게든 다항 시간에 배낭 문제를 해결한 것이다. 당신은 이론적인 응용에는 관심이 없으므로, 곧바로 친구의 아파트로 돌아가 배낭을 최적으로 싸기로 한다.

도착해 보니 친구는 이미 자신만의 해법, 즉 가능한 모든 포장을 열거하는 방법을 택해 두었다. 당신이 가져가고 싶어 했던 모든 물건이 아파트 전체에 흩어져 있고, 그것들을 다시 모으는 데는 아주 오랜 시간이 걸릴 것이다.

다행히도 당신은 친구가 해 둔 작업을 활용할 수 있다. 당신이 가져갈 수 있는 모든 부분집합에 대해 친구는 그 물건들의 총 무게를 적어 두었다. 그러나 어떤 물건이 그 합에 포함되었는지는 적어 두지 않았으므로, 각 총 무게에 어떤 물건이 기여했는지 알 수 없다. 물건의 원래 무게가 음이 아닌 정수의 모임 (a1, ..., an)을 이룬다면, 친구는 다음과 같은 중복집합을 적어 둔 것이다.

[S\left(\left(a_1, \dots, a_n\right)\right) := \left{ \sum_{i \in I}{a_i} \mid I \subseteq \left{ 1, \dots , n \right} \right}\text{ .} ]

예를 들어 친구에게 물건이 둘 있고 그 무게가 2, 3이라면, 친구는 다음을 적어 두었다.

• 0, 공집합 {}에 대응한다.
• 2, 부분집합 {2}에 대응한다.
• 3, 부분집합 {3}에 대응한다.
• 5, 부분집합 {2, 3}에 대응한다.

당신은 배낭 알고리즘을 쓰기 시작할 수 있도록 개별 물건의 무게를 모두 복원하려 한다. 친구가 이 무게들을 더하다가 실수했을 수도 있으므로, 그 목록이 일관되지 않을 수도 있다.

• 한 줄에 물건의 수를 나타내는 정수 1 ≤ n ≤ 18이 주어진다.
• 2n개의 줄이 주어지며, 각 줄에는 부분집합의 총 무게를 나타내는 정수 0 ≤ w ≤ 228이 하나씩 있다. 모든 부분집합이 정확히 한 번씩 나타난다.

S((a1, ... , an)) = {b1, ... , b2n}을 만족하는 음이 아닌 정수 a1, ... , an을 비감소 순서로 n개의 줄에 출력한다. 그러한 정수가 존재하지 않으면 impossible을 한 줄에 출력한다.