Given a directed graph $G$ with $n$ nodes and $m$ edges, nodes are numbered from $1$ to $n$. The $i$-th edge ($1 \le i \le m$) points from $u_i$ to $v_i$, with the guarantee that $u_i < v_i$. Each node $j$ ($1 \le j \le n$) has two weights $a_j$ and $b_j$, where $[a_1, \dots, a_n]$ and $[b_1, \dots, b_n]$ are both permutations of $1 \sim n$.

You need to perform $q$ operations. There are three types of operations:

• 1 x y: Swap $a_x$ and $a_y$.
• 2 x y: Swap $b_x$ and $b_y$.
• 3 x l r: You need to output the maximum value of $b_y$ among all nodes $y$ that satisfy the following two conditions. If no such node exists, output $0$:
  1. $l \le a_y \le r$.
  2. There exists a directed path from $x$ to $y$ in graph $G$. That is, there exist an integer $k \ge 1$ and $k$ nodes $p_1, p_2, \dots, p_k$ such that $p_1 = x$, $p_k = y$, and for all $1 \le i < k$, there exists a directed edge from $p_i$ to $p_{i+1}$ in $G$. Specifically, there is always a directed path from $x$ to $x$ in $G$.

Input

The input is read from the file recall.in.

There are multiple test cases. The first line contains two integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. The following lines contain the data for each test case.

For each test case: The first line contains three integers $n, m, q$, representing the number of nodes, the number of edges, and the number of operations, respectively. The next $m$ lines each contain two integers $u_i, v_i$ ($1 \le i \le m$), describing an edge. The next line contains $n$ integers $a_1, a_2, \dots, a_n$, describing the $a$ weight of each node. The next line contains $n$ integers $b_1, b_2, \dots, b_n$, describing the $b$ weight of each node. * The last $q$ lines each contain three or four integers $o_i, x_i, y_i$ or $o_i, x_i, l_i, r_i$, describing an operation, with the format as defined in the problem description.

Output

Output to the file recall.out.

For each operation of type 3, output one integer per line, representing the answer to the corresponding operation.

Examples

Input 1

1 0
4 4 7
1 2
1 3
2 4
3 4
4 2 3 1
1 3 2 4
3 2 1 3
3 3 2 4
1 1 4
3 1 1 3
2 2 4
3 1 2 3
3 4 1 1

Output 1

4
2
3
4
0

Note 1

This sample contains 1 test case with 7 operations. For the first operation, all nodes satisfying the conditions are $2, 4$, so the answer is $\max\{b_2, b_4\} = 4$. For the second operation, the only node satisfying the conditions is $3$, so the answer is $b_3 = 2$. For the third operation, after swapping $a_1, a_4$, the weight sequence $a$ becomes $[1, 2, 3, 4]$. For the fourth operation, all nodes satisfying the conditions are $1, 2, 3$, so the answer is $\max\{b_1, b_2, b_3\} = 3$. For the fifth operation, after swapping $b_2, b_4$, the weight sequence $b$ becomes $[1, 4, 2, 3]$. For the sixth operation, all nodes satisfying the conditions are $2, 3$, so the answer is $\max\{b_2, b_3\} = 4$. * For the seventh operation, no nodes satisfy the conditions, so the answer is $0$.

Examples

Input 2

(See recall/recall2.in in the contestant directory)

Output 2

(See recall/recall2.ans in the contestant directory)

Note 2

This sample satisfies the constraints of test cases $1 \sim 5$.

Input 3

(See recall/recall3.in in the contestant directory)

Output 3

(See recall/recall3.ans in the contestant directory)

Note 3

This sample satisfies the constraints of test case $7$.

Input 4

(See recall/recall4.in in the contestant directory)

Output 4

(See recall/recall4.ans in the contestant directory)

Note 4

This sample satisfies the constraints of test cases $10 \sim 12$.

Input 5

(See recall/recall5.in in the contestant directory)

Output 5

(See recall/recall5.ans in the contestant directory)

Note 5

This sample satisfies the constraints of test cases $13, 14$.

Input 6

(See recall/recall6.in in the contestant directory)

Output 6

(See recall/recall6.ans in the contestant directory)

Note 6

This sample satisfies the constraints of test case $18$.

Input 7

(See recall/recall7.in in the contestant directory)

Output 7

(See recall/recall7.ans in the contestant directory)

Note 7

This sample satisfies the constraints of test cases $23 \sim 25$.

Subtasks

For all test cases: $1 \le T \le 3$ $1 \le n, q \le 10^5$, $1 \le m \le 2 \times 10^5$ $\forall 1 \le i \le m, 1 \le u_i < v_i \le n$ $\forall 1 \le i \le n, 1 \le a_i \le n$, and $[a_1, \dots, a_n]$ is a permutation of $1 \sim n$ $\forall 1 \le i \le n, 1 \le b_i \le n$, and $[b_1, \dots, b_n]$ is a permutation of $1 \sim n$ $\forall 1 \le i \le q, o_i \in \{1, 2, 3\}, 1 \le x_i, y_i \le n, 1 \le l_i \le r_i \le n$

• Special Property A: $\forall 1 \le i \le q, o_i \neq 1$.
• Special Property B: $\forall 1 \le i \le q, o_i \neq 2$.
• Special Property C: $\forall 1 \le i \le q, l_i = 1, r_i = n$.
• Special Property D: Guaranteed that at the time of every type 3 operation, $\forall 1 \le i \le n, a_i = b_i$.

Note

Please pay attention to the special time and memory limits of this problem.