该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

我们称位置 $x$ 和 $y$ 是相邻的，当且仅当对于每个 $i=1, 2, \ldots, N$，以下条件成立：

• 设 $x'$ 和 $y'$ 分别为 $x$ 和 $y$ 的三进制表示中从右数第 $i$ 位的数字，则 $|x' - y'| \leq 1$。

已知位置 $i$ 的所有相邻位置上总共有恰好 $A_i$ 个炸弹。请输出一个符合该信息的炸弹布局。

输入格式

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

$N$

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

• $1 \leq N \leq 12$
• 存在至少一个符合 $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
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