题目描述

JOHNKRAM 最近在研究排序网络，但他发现他不会制作比较器，于是他用交换器来代替比较器。

一个交换器有两个输入端 $ x, y $ 和两个输出端 $ x', y' $。如果交换器处于关闭状态，则 $ x $ 收到的信号会从 $ x' $ 发出，$ y $ 收到的信号会从 $ y' $ 发出。如果交换器处于开启状态，则 $ x $ 收到的信号会从 $ y' $ 发出。

JOHNKRAM 设计了这样一个递归定义的网络：

• $ 1 $ 阶网络就是一个交换器。
• $ n(n > 1) $ 阶网络的第一排是 $ 2 ^ {n - 1} $ 个交换器，接下来是两个 $ n - 1 $ 阶网络,最后一排也是 $ 2 ^ {n - 1} $ 个交换器。将第一排的输出端和第二排的输入端分别从左到右标号为 $ 0 \sim 2 ^ n - 1 $，第一排的 $ i $ 输出端连接到第二排的 $ i \mathbin{\texttt{>>}} 1 $ 输入端，其中 $ \mathbin{\texttt{>>}} $ 指 $ n $ 位二进制数的循环右移。类似，将倒数第一排的输入端和倒数第二排的输出端分别从左到右标号为 $ 0 \sim 2 ^ n - 1 $，倒数第二排的 $ i $ 输出端连接到倒数第一排的 $ i \mathbin{\texttt{<<}} 1 $ 输入端，其中 $ \mathbin{\texttt{<<}} $ 指 $ n $ 位二进制数的循环左移。

一个 $ 3 $ 阶的网络如下图所示：

JOHNKRAM 通过开关交换器来调整网络。现在他对一个 $ n $ 阶网络的 $ 2 ^ n $ 个输入端分别输入了一个数，第 $ i(0 < i < 2 ^ n) $ 个输入端输入的是 $ i $。然后他给出了一个长度为 $ 2 ^ n $ 的排列 $ p $。他希望你给出一种网络的状态，使得第 $ i(0 < i < 2 ^ n) $ 个输出端输出的是 $ p_i $。

输入格式

输入文件包含不超过 10 组测试数据。
每个测试数据包含两行，第一行一个整数 $ n $，表示是一个 $ n $ 阶网络。
第二行 $ 2 ^ n $ 个整数，表示排列 $ p $。
输入文件以一个 0 结尾。

输出格式

对于每组数据，如果没有合法的解，则输出 $ -1 $，否则输出 $ 2n - 1 $ 行 $ 2 ^ n $ 位二进制数，表示网络状态。如果一个交换器是开启的，则对应的位置上是 $ 1 $，否则是 $ 0 $。如果有多解，输出字典序最小的。

每个答案后打印一个空行。

样例

input

2
3 2 1 0
3
3 7 4 0 2 6 1 5
0

output

00
11
11

0011
0000
0110
1111
1101

数据范围与提示

对于 $ 20\% $ 的数据，保证 $ n \leq 3 $；
对于 $ 100\% $ 的数据，保证 $ 1 \leq n \leq 13 $。