题目描述

在位置 $0, 1, 2, \\ldots, 3^N-1$ 中的每个位置上都有零或一个炸弹。
如果且仅当对于每个 $i=1, \\ldots, N$，满足以下条件时，位置 $x$ 和 $y$ 互为相邻。

• 令 $x'$ 和 $y'$ 分别表示 $x$ 和 $y$ 的第 $i$ 小的三进制位数，则 $|x' - y'| \\leq 1$。

已知在与位置 $i$ 相邻的位置处总共有 $A_i$ 个炸弹。请打印出与该信息一致的炸弹布置。

约束条件

• $1 \\leq N \\leq 12$
• 存在一个与 $A_0, A_1, \\ldots, A_{3^N-1}$ 一致的炸弹布置。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

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

输出

用空格分隔打印 $B_0, B_1, \\ldots, B_{3^N-1}$，其中 $B_i = 0$ 表示位置 $i$ 没有炸弹，$B_i = 1$ 表示位置 $i$ 有炸弹。

示例输入 1

1
0 1 1

示例输出 1

0 0 1

位置 $0$ 与位置 $0$ 和 $1$ 相邻，它们总共有 $0$ 个炸弹。
位置 $1$ 与位置 $0$、$1$ 和 $2$ 相邻，它们总共有 $1$ 个炸弹。
位置 $2$ 与位置 $1$ 和 $2$ 相邻，它们总共有 $1$ 个炸弹。
如果只在位置 $2$ 放置一个炸弹，上述所有条件都满足，所以这种布置是正确的。

示例输入 2

2
2 3 2 4 5 3 3 4 2

示例输出 2

0 1 0 1 0 1 1 1 0

示例输入 3

2
0 0 0 0 0 0 0 0 0

示例输出 3

0 0 0 0 0 0 0 0 0