题目描述

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

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

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

1. 1 阶网络就是一个交换器。
2. $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$。如果有多解，输出字典序最小的。

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

样例

输入

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

输出

00
11
11

0011
0000
0110
1111
1101

数据范围与提示

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