You are given a 2D array $A$ with $n$ rows and $m$ columns. There are $q$ queries of either form:

• $1 \; i \; j$: swap row $i$ and row $j$.
• $2 \; i \; j$: swap column $i$ and column $j$.

Print array $A$ after all $q$ queries. It is guaranteed that all queries are valid.

Input

• The first line contains 3 integers $n, m, q$.
• The next $n$ lines, each line contains $m$ integers representing array $A$.
• Next $q$ lines, each line contains 3 integers $1 \; i \; j$ or $2 \; i \; j$.

Output

• $n$ lines, each lines contains $m$ integers represent array $A$ after $q$ queries.

Constraints

• $1 \le n, m, q \le 100$.
• $|A_{i, j}| \le 100$.

Example

Input:

2 2 2
1 2
3 4
1 1 2
2 1 2

Output:

4 3
2 1