题目描述

小 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$ 列。

请你输出复原后的拼图。

输入格式

第一行，两个正整数 $n$ 和 $m$，分别表示拼图的边长和总操作次数。

接下来 $n$ 行，每行 $n$ 个正整数 $A_{i,j}$，表示拼图上第 $i$ 行，第 $j$ 列上的数字。

接下来 $m$ 行，每行三个正整数 $op,x,y$，其中 $op$ 表示操作类型，$x,y$ 代表被操作的行号或列号。

输出格式

输出共 $n$ 行，每行 $n$ 个正整数，表示复原后的拼图。

样例 #1

样例输入 #1

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

样例输出 #1

4 6 5
3 1 2
9 7 8

样例 #2

样例输入 #2

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

样例输出 #2

11 13 12
31 33 32
21 23 22

样例 #3

样例输入 #3

4 4
12 32 42 82
53 43 34 98
90 32 42 53
37 17 88 10
0 2 4
1 2 4
0 1 4
1 1 3

样例输出 #3

32 53 42 90
17 10 88 37
32 82 42 12
43 98 34 53

提示

数据范围

对于前 $30\%$ 的数据，保证每一行数字相同；对于前 $60\%$ 的数据，保证 $1\leq m\leq 3\times 10^3$。

对于 $100\%$ 的数据，保证 $1\leq m\leq 10^6$，$1\leq n,A_{i,j}\leq 10^3$，$1\leq x,y\leq n$，$0\leq op\leq 1$。