問題文

mentoscola君は以下の問題を解きました。

  • 問題
    NN 個の正整数が昇順に並べられた数列 AA が与えられます。
    AA の空でない全ての部分列について、それぞれの和を考えます。
    それぞれの和を昇順に並べた長さ 2N12^N-1 の正整数列 SS を出力してください。

mentoscola君はこの問題を解いて数列 SS を求めた後、元の数列 AA を忘れてしまいました。

数列 SS が与えられるので、数列 AA を復元してください。
当てはまる数列 AA が存在しない場合はそれを報告してください。

制約

  • 1N161\leq N \leq 16
  • 1Si1091\leq S_i \leq 10^9 (1i2N1)(1\leq i \leq 2^N-1)
  • SS は昇順

入力

入力はすべて整数です

NN
S1S_1 S2S_2 ...... S2N1S_{2^N-1}

出力

長さ NN からなる数列 AA を復元し、11 行に出力してください。
当てはまる数列 AA が存在しない場合は 「-1」を出力してください。

サンプル

入力1
3
1 2 3 3 4 5 6
出力1
1 2 3

元の数列 AA は昇順になっていることに注意してください。


入力2
2
10 100 1000
出力2
-1

あてはまる AA が存在しない場合もあります。


入力3
4
2 3 4 5 6 7 7 9 9 10 11 12 13 14 16
出力3
2 3 4 7

Submit


Go (1.21)