Problem Description

Xiao S has a peculiar mechanical puzzle. This puzzle can be seen as a square matrix $A$ with $n$ rows and $n$ columns, where each position at the $i$-th row and $j$-th column contains a positive integer $A_{i, j}$.

Unlike ordinary puzzles, the numbers on this mechanical puzzle cannot be moved arbitrarily. They must be operated according to one of the following rules:

• Select the $x$-th row and the $y$-th row of the puzzle and swap these two rows;
• Select the $x$-th column and the $y$-th column of the puzzle and swap these two columns.

To restore the puzzle, Xiao S will perform a total of $m$ operations. Each operation is formatted as follows:

• 1 x y, indicating to swap the $x$-th row and the $y$-th row;
• 0 x y, indicating to swap the $x$-th column and the $y$-th column.

Please output the restored puzzle.

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of rows and columns of the puzzle and the total number of operations, respectively.
The next $n$ lines, each containing $n$ positive integers $A_{i, j}$, represent the numbers on the puzzle at the $i$-th row and $j$-th column.
The next $m$ lines, each containing three positive integers $op, x, y$, where $op$ indicates the type of operation, and $x, y$ represent the row or column numbers being operated on.

Output Format

Output $n$ lines, each containing $n$ positive integers, representing the restored puzzle.

Sample Input and Output

Input Sample #1

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

Output Sample #1

4 6 5 
3 1 2 
9 7 8

Input Sample #2

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

Output Sample #2

11 13 12 
31 33 32 
21 23 22

Input Sample #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

Output Sample #3

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

Notes

Sample 1 Explanation

The first operation swaps the $2$-nd column and the $3$-rd column; the second operation does not change anything.

Sample 2 Explanation

The first operation swaps the $2$-nd row and the $3$-rd row, changing the puzzle to:
$$ \begin{aligned} 11 \ 12 \ 13\\ \textcolor{red}{31 \ 32 \ 33}\\ \textcolor{blue}{21 \ 22 \ 23} \end{aligned} $$

The second operation swaps the $2$-nd column and the $3$-rd column, changing the puzzle to:
$$ \begin{aligned} 11 \ \textcolor{red}{13} \ \textcolor{blue}{12} \\ 31 \ \textcolor{red}{33} \ \textcolor{blue}{32} \\ 21 \ \textcolor{red}{23} \ \textcolor{blue}{22} \end{aligned} $$

Data Range

For the first $30\%$ of the data, it is guaranteed that each row contains the same numbers;
For the first $60\%$ of the data, it is guaranteed that $1 \leq m \leq 3 \times 10^3$.
For $100\%$ of the data, it is guaranteed that $1 \leq m \leq 10^6, 1 \leq n, A_{i, j} \leq 10^3, 1 \leq x, y \leq n$, and $0 \leq op \leq 1$.

见题面 Input 部分

见题面 Output 部分