Restore the Puzzle

You are given a square matrix ( A ) of size ( n\times n ) (i.e., ( n ) rows and ( n ) columns) where each element ( A_{i,j} ) is a positive integer. You need to perform ( m ) operations to restore the puzzle. Each operation is either swapping two rows or swapping two columns. The operations are provided in the following format:

• 1 x y : Swap row \( x \) with row \( y \).
• 0 x y : Swap column \( x \) with column \( y \).

After executing all ( m ) operations, output the resulting matrix. Note that the rows and columns are 1-indexed.

inputFormat

The first line contains two integers ( n ) and ( m ) (( 1 \leq n \leq 1000 ), ( 0 \leq m \leq 10000 )) representing the size of the matrix and the number of operations.

The next ( n ) lines each contain ( n ) positive integers representing the matrix ( A ).

Then ( m ) lines follow, each line contains one operation in one of the following formats:

• 1 x y : Swap row \( x \) with row \( y \).
• 0 x y : Swap column \( x \) with column \( y \).

It is guaranteed that all operations are valid.

outputFormat

Output the restored matrix after all operations. Print ( n ) lines, each containing ( n ) space-separated integers.

sample

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

7 9 8
4 6 5
1 3 2