题面翻译

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

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

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

样例 #1

样例输入 #1

1
0 1 1

样例输出 #1

0 0 1

样例 #2

样例输入 #2

2
2 3 2 4 5 3 3 4 2

样例输出 #2

0 1 0 1 0 1 1 1 0

样例 #3

样例输入 #3

2
0 0 0 0 0 0 0 0 0

样例输出 #3

0 0 0 0 0 0 0 0 0

提示

制約

• $1\ \leq\ N\ \leq\ 12$