当前没有测试数据。

G - 3^N 扫雷

得分：$600$ 分

问题描述

在位置 $0, 1, 2, \ldots, 3^N-1$ 上分别放置零个或一个炸弹。 如果满足以下条件，则称位置 $x$ 和 $y$ 是 相邻 的： 对于每个 $i=1, \ldots, N$， 设 $x$ 和 $y$ 的十进制表示中的第 $i$ 个最低位分别为 $x'$ 和 $y'$，则 $|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

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

样例 2

略

样例 3

所有位置都没有炸弹。