配点 : $600$ 点

問題文

位置 $0, 1, 2, \ldots, 3^N-1$ にそれぞれ $0$ 個あるいは $1$ 個の爆弾があります。 また、位置 $x$ と位置 $y$ は $i=0,1, \ldots, N-1$ すべてに対し以下の条件を満たすとき、またそのときに限り近い位置であるとします。

• $x, y$ を $3$ 進表記したときの $3^i$ の位の数字をそれぞれ $x', y'$ として、$|x' - y'| \leq 1$ が成立する。

位置 $i$ と近い位置にある爆弾の個数が $A_i$ 個であるとわかっているとき、爆弾の配置としてありえるものを $1$ つ出力してください。

制約

• $1 \leq N \leq 12$
• $A_0, A_1, \ldots, A_{3^N-1}$ に対応する爆弾の配置が存在する
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_0$ $A_1$ $\ldots$ $A_{3^N-1}$

出力

位置 $i$ に爆弾がないとき $B_i = 0$ 、位置 $i$ に爆弾があるとき $B_i = 1$ として $B_0, B_1, \ldots, B_{3^N-1}$ を空白区切りで出力せよ。

1
0 1 1

0 0 1

$0$ と近い位置は $0$ と $1$ で、位置 $0$ と位置 $1$ に爆弾は合計で $0$ 個あります。 $1$ と近い位置は $0$ と $1$ と $2$ で、位置 $0$ と位置 $1$ と位置 $2$ に爆弾は合計で $1$ 個あります。 $2$ と近い位置は $1$ と $2$ で、位置 $1$ と位置 $2$ に爆弾は合計で $1$ 個あります。 $2$ にのみ爆弾があるような配置は上の条件を全て満たすため、正答となります。

2
2 3 2 4 5 3 3 4 2

0 1 0 1 0 1 1 1 0

2
0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0