There are two trees, Tree A and Tree B. Tree A is underdeveloped, while Tree B is well-developed.

To catch up with Tree B's development, Tree A has begun a process of modification.

Tree A has $n$ nodes, and Tree B has $m$ nodes. Each node has a color. Both Tree A and Tree B are rooted at node 1.

To catch up with Tree B, Tree A performs $q$ development operations.

For each operation, first read an integer $P$ representing the operation type.

If $P=1$, it represents a query. Then read four integers $P_1, P_2, P_3, P_4$.

Let $lt$ be the answer to the previous query (initially $lt=0$). Let $D_1=P_3\oplus lt$ and $D_2=P_4\oplus lt$.

Tree A wants you to answer how many distinct colors are present among the nodes in the subtree of $P_1$ in Tree A that are at a distance of at most $D_1$ from $P_1$, and the nodes in the subtree of $P_2$ in Tree B that are at a distance of at most $D_2$ from $P_2$.

If $P=2$, it represents a modification operation on Tree A. Then read two integers $S_1, S_2$, indicating that the color of node $S_1$ in Tree A is changed to $S_2$.

Input

The first line contains three integers $n, m, q$.

The next $n-1$ lines each contain two positive integers $u, v$, representing an edge between $u$ and $v$ in Tree A.

Then, $m-1$ lines each contain two positive integers $u, v$, representing an edge between $u$ and $v$ in Tree B.

Next, $n$ lines each contain a positive integer $v_1$, where the $i$-th line represents the color of node $i$ in Tree A.

Then, $m$ lines each contain a positive integer $v_2$, where the $i$-th line represents the color of node $i$ in Tree B.

Finally, read $q$ queries. See the problem description for the query format.

Output

For each query, output a single integer on a new line representing the answer.

Examples

Input 1

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

Output 1

2
2
2
2
3

Subtasks

$n\leq 20$, $m\leq 2\times 10^5$, $q\leq 10^6$

$P_1\leq n$, $P_2\leq m$, $1\leq P_3,P_4\leq 2\times 10^5$

• Subtask 1 ($10\%$): $m, q \le 2\,000$
• Subtask 2 ($20\%$): No type 2 operations exist.
• Subtask 3 ($30\%$): $m, q \le 10^5$
• Subtask 4 ($10\%$): $n = 1$
• Subtask 5 ($30\%$): No special restrictions.