3^N 扫雷

题目描述

位置 $0, 1, 2, \ldots, 3^N-1$ 上各放置 0 个或 1 个炸弹。

当且仅当对每个 $i=1, \ldots, N$,下面条件都成立时,称位置 $x$ 与位置 $y$ 相邻。

设 $x'$ 和 $y'$ 分别为 $x$ 和 $y$ 的三进制表示中从低到高第 $i$ 位的数字。此时 $|x' - y'| \leq 1$。

已知与位置 $i$ 相邻的位置上的炸弹总数恰好为 $A_i$。输出一个与这些信息一致的炸弹放置方案。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

用空格隔开输出 $B_0, B_1, \ldots, B_{3^N-1}$,其中若位置 $i$ 没有炸弹则 $B_i = 0$,若有炸弹则 $B_i = 1$。

样例

1
0 1 1

0 0 1

位置 $0$ 与位置 $0$、$1$ 相邻,炸弹总数为 0。

位置 $1$ 与位置 $0$、$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

数据范围

• $1 \leq N \leq 12$
• 存在与 $A_0, A_1, \ldots, A_{3^N-1}$ 一致的炸弹放置方案。
• 输入中的所有值均为整数。