题目描述

在被三个小时的手速练习折磨后，绝望的小 A 恳求你编写一个程序，将给定的谱面转换为纯跳键谱面。

形式化地说，一个谱面是一个 $n \times 4$ 的二进制矩阵。设 $c_{i,j}$ 表示第 $i$ 行第 $j$ 列的元素，其中：

• $c_{i,j}=1$ 表示该位置有一个音符
• $c_{i,j}=0$ 表示该位置为空

给定的谱面保证：任意一列都不会出现两个连续的音符。也就是说，对于所有满足 $1 < i \le n$ 且 $1 \le j \le 4$ 的位置，都有：

在演奏时：

• 左手负责击打第 $1$ 列和第 $2$ 列的音符
• 右手负责击打第 $3$ 列和第 $4$ 列的音符

为了让谱面更容易演奏，小 A 希望保证：同一只手不需要在相邻两行都击打音符。

为此，你需要对谱面执行如下变换：

按逆序检查所有行：从第 $n-1$ 行到第 $1$ 行。

对于当前行 $i$：

• 如果第 $i+1$ 行在第 $1$ 或第 $2$ 列有音符，并且第 $i$ 行也在第 $1$ 或第 $2$ 列有音符，那么就将第 $i$ 行中的这个音符下移一行 （可以证明，此时这样的音符至多只有一个，且其下方位置一定为空）

• 类似地，如果第 $i+1$ 行在第 $3$ 或第 $4$ 列有音符，并且第 $i$ 行也在第 $3$ 或第 $4$ 列有音符，那么就将第 $i$ 行中的这个音符下移一行

经过上述变换后，谱面就会变成纯跳键谱面。请你输出变换后的结果。

数据范围

• $1 \le n \le 10^3$

对于部分数据：

• $50$ 的数据满足：$n \le 100$
• $100$ 的数据无特殊限制

输入格式

从标准输入按以下格式读取数据：

$n$

第 $1$ 行的 4 个二进制数字

第 $2$ 行的 4 个二进制数字

$\vdots$

第 $n$ 行的 4 个二进制数字

其中：

• 第一行输入一个整数 $n$，表示谱面的行数。
• 接下来 $n$ 行，每行包含一个长度为 $4$ 的二进制串，表示该行 4 列中是否存在音符。

保证输入中没有任何一列会出现两个连续的 1。

输出格式

输出 $n$ 行，每行一个长度为 $4$ 的二进制串，表示变换后的谱面。

不要输出任何额外的空格或空行。

样例

4
1011
0100
1001
0010

1011
0000
1100
0011

20
0011
0100
1001
0010
0100
1000
0110
0001
1010
0100
0011
1100
0011
0100
0011
1100
0011
0100
1010
0001

0011
0000
1100
0011
0100
0000
1110
0000
0011
1100
0011
1100
0011
0100
0011
1100
0011
0000
1100
0011