题目描述

水能自己找到迷宫出口吗？这是一个有趣的实验。

既然能用实验的形式模拟，就也能以程序的形式模拟。

给你一个$N\times N$的迷宫，我们定义每个格子可能在上下左右四个方向有挡板。保证所给的迷宫，将每一个格子当点提取出来以后，恰好构成了一棵树(跟起点不连通的点不在考虑范围）。迷宫的入口一定在整个迷宫的顶端，出口一定在整个迷宫的底端。

我们假设把这个迷宫放在真空（没有气压）且有重力的环境中，从时刻$0$开始，以非常缓慢的速度从迷宫的正上方开始滴水，那么持续的滴水将逐渐在迷宫中行走，直到某一刻开始，从迷宫的出口流出去。

现在，我们的问题是：在无穷久以后，哪些坐标的格子曾经有水流经过，以及，哪些坐标的格子，此时已经充满了水。

输入格式

第一行输入三个数字$N,X,Y$，$N$表示迷宫的大小，$X$表示迷宫上方的入口是第几列，$Y$表示迷宫下方的出口是第几列。

接下来$N$行，每行$N$个数字，要么是$0$要么是$1$，表示第$i$行第$j$列的格子，上方有没有挡板。

接下来一个空行（主要是看起来方便）。

接下来$N$行，每行$N$个数字，要么是$0$要么是$1$，表示第$i$行第$j$列的格子，左方有没有挡板。

输出格式

输出一个$N\times N$的矩阵，每个位置输出$0,1,2$三种数字之一，$0$代表没有水经过，$1$代表有水经过，但是没有蓄水，$2$代表蓄满了水。

输出格式

输出$N$个正整数表示答案。

样例输入 #1

4 1 1
0 1 1 1
0 0 0 0
1 1 1 0
0 0 0 0

1 1 0 0
1 0 1 1
1 1 0 0
1 0 1 1

样例输出 #1

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

样例解释 #1

样例输入 #2

10 6 5
1 1 1 1 1 0 1 1 1 1
0 0 0 1 0 1 1 0 0 1
0 0 1 0 1 0 1 0 1 0
1 1 0 1 0 0 0 1 0 0
0 1 0 0 0 0 1 1 1 0
0 0 1 1 1 1 0 0 0 1
0 0 0 0 1 0 0 1 1 0
1 1 0 1 0 1 0 0 1 0
0 1 1 0 0 0 1 1 1 0
1 0 0 1 0 1 0 0 1 0

1 1 0 0 1 0 1 0 1 0
1 1 1 1 0 1 0 0 1 0
1 0 0 0 0 1 1 0 1 0
1 0 0 1 1 1 1 0 0 1
1 0 1 0 1 0 1 0 1 0
1 1 1 1 0 0 1 1 0 1
1 1 1 1 0 1 0 1 0 1
1 0 0 1 0 1 1 0 0 0
1 0 1 0 1 1 0 1 0 0
1 0 0 0 1 0 1 0 1 0

样例输出 #2

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

样例解释 #2

需要注意的是，坐标$(2,1),(2,2),(6,10)$也会有一滴水。

样例输入 #3

6 1 1
0 1 1 1 1 1
0 0 0 0 0 0
1 1 0 1 0 1
0 1 1 0 0 0
1 0 0 0 1 0
0 1 0 0 0 0

1 1 0 1 0 0
1 0 1 1 1 1
1 0 0 0 1 0
1 0 1 1 0 1
1 0 1 1 1 1
1 0 1 0 0 1

样例输出 #3

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

样例解释 #3

数据范围

对于30%的数据：$N\leq 10$。

对于编号为奇数的测试点：保证水流在任意时刻都不会向上流。

对于100%的数据：$N\leq 1000$。

评分方式

如果答案中该输出$0$的部分你输出了$0$，该输出$1$或$2$的部分你输出了$1$或者$2$（无论是否正确），则你可以得到这个点$70\%$的分数。

如果你的输出完全正确，则你可以得到这个点$100\%$的分数。