Jessie 最近开始慢跑，并用运动手环记录运动进度。附近的一座山上有 $n$ 个极佳的景点。由于对于业余慢跑者来说跑上坡很困难，Jessie 只打算跑下坡。景点的编号为 $1$ 到 $n$，编号越大，景点的海拔越低。某些景点对之间由小路连接。在我们的问题中，我们只考虑小路 $i \to j$（从海拔较高的景点到海拔较低的景点，即 $i < j$）。

Jessie 成功完成了若干次慢跑。对于每一种可能的景点序列（满足序列中任意两个相邻景点之间都存在小路），她都恰好跑过了一次。现在，Jessie 计划利用运动手环收集的数据来还原所有小路的地图。不幸的是，手环的屏幕很小，只能显示 Jessie 在每对景点 $i$ 和 $j$（其中 $1 \le i < j \le n$）之间进行的慢跑次数的最后一位数字。你能帮 Jessie 根据这些数据还原山上的小路地图吗？

输入格式

输入的第一行包含一个整数 $n$，表示山上的景点数量（$2 \le n \le 500$）。

接下来 $n$ 行：第 $i$ 行包含 $n$ 个字符 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$。字符 $a_{i,j}$ 表示 Jessie 从第 $i$ 个景点出发并在第 $j$ 个景点结束的不同慢跑次数的最后一位数字。对于所有的 $i \ge j$，有 $a_{i,j} = 0$。

保证对于给定的输入数据，总是存在解。

输出格式

输出 $n$ 行，以类似的格式描述山上的地图：第 $i$ 行应包含 $n$ 个字符，如果存在一条从第 $i$ 个景点到第 $j$ 个景点的小路，则第 $j$ 个字符为 1，否则为 0。对于所有的 $i \ge j$，第 $i$ 行的第 $j$ 个字符必须为 0。

样例

输入样例 1

5
01113
00012
00001
00001
00000

输出样例 1

01100
00011
00001
00001
00000