题目描述

在一个由数字0构成的方阵中，存在一个由数字1形成的屏障。方阵中只有一个屏障，该屏障仅通过上下左右四个方向延伸，并将方阵划分为内部和外部两个区域。你的任务是将屏障外部的所有0修改为2，而内部的0保持不变。

输入格式

第一行输入一个整数n（1 ≤ n ≤ 30），表示方阵的大小。
接下来输入n行，每行是一个长度为n的字符串，由字符'0'和'1'组成（无空格分隔）。

输出格式

输出处理后的方阵，每个字符用空格分隔，共n行。

样例数据

input

6
000000
001111
011001
110001
100001
111111

output

2 2 2 2 2 2  
2 2 1 1 1 1  
2 1 1 0 0 1  
1 1 0 0 0 1  
1 0 0 0 0 1  
1 1 1 1 1 1

提示

屏障形成的闭合区域内部至少有一个0。
输入保证存在且仅存在一个闭合屏障。