题目描述

位置 $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$ つ出力してください。

输入格式

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

$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}$ を空白区切りで出力せよ。

题目大意

位置 $0\sim 3^n-1$ 中有若干个雷，你需要找出这些雷，其中，每个位置至多有一个雷。

我们定义两个位置 $i$ 和 $j$ 是相邻的，当且仅当 $i$ 和 $j$ 在三进制表示下的每一位的差的绝对值都小于等于 $1$。（当然，自己也算与自己相邻）

现在，对于每一个位置 $i$，$A_i$ 表示与位置 $i$ 相邻的位置中雷的个数，请根据给定 $A$ 输出每个位置雷的个数。

1
0 1 1

0 0 1

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

提示

制約

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

Sample Explanation 1

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