9426 - 拼图

小 S 有一个奇怪的机关拼图。这个拼图可以看作一个n行n列的方阵A,第i行第j列的位置上有一个正整数A(i,j)。
与寻常拼图不同的是,这个机关拼图上的数字不能随意移动,必须按照如下规则之一操作:
选择拼图上的第x行和第y行,交换这两行;
选择拼图上的第x列和第y列,交换这两列。
为了复原这个拼图,小 S 将会操作共m次,每次操作格式如下:
1 x y,表示交换第x行和第y行;
0 x y,表示交换第x列和第y列;
请你输出复原后的拼图。

输入

从文件picture.in中读入数据。
第一行,两个正整数n和m,分别表示拼图的行数、列数和总操作次数。
接下来n行,每行n 个正整数A(i,j),表示拼图上第i行,第j列上的数字。
接下来m行,每行三个正整数op,x,y,其中op表示操作类型x,y代表被操作的行号或列号。

输出

输出到文件picture.out中。
输出共n行,每行n个正整数,表示复原后的拼图。

样例

输入

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

输出

4 6 5 
3 1 2 
9 7 8

输入

3 2
11 12 13
21 22 23
31 32 33
1 2 3
0 2 3

输出

11 13 12 
31 33 32 
21 23 22

提示

【样例2解释】
第一次操作,交换第2行和第3行,拼图变为:

第二次操作,交换第2列和第3列,拼图变为:

【数据范围】
对于100%的数据:1≤m≤10^6,1≤n,A(i,j)≤10^3,1≤x,y≤n,0≤op≤1。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题