Swapping Permutations and Graph Reachability Query

Given a directed acyclic graph \(G\) with \(n\) nodes and \(m\) edges. The nodes are numbered from \(1\) to \(n\). For each edge \(i\) (\(1 \leq i \leq m\)), there is a directed edge from \(u_i\) to \(v_i\) with \(u_i .

You are required to process \(q\) operations of three types:

1. \(1\ x\ y\): Swap \(a_x\) and \(a_y\).
2. \(2\ x\ y\): Swap \(b_x\) and \(b_y\).
3. \(3\ x\ l\ r\): Among all nodes \(y\) satisfying the following conditions, output the maximum value of \(b_y\). If no such node exists, output \(0\).
   1. \(l \leq a_y \leq r\);
   2. There exists a directed path from \(x\) to \(y\) in \(G\) (note that a node always has a path to itself).

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\). The second line contains \(n\) integers representing the permutation \(a\). The third line contains \(n\) integers representing the permutation \(b\). The next \(m\) lines each contain two integers \(u_i\) and \(v_i\) representing a directed edge from \(u_i\) to \(v_i\). The following \(q\) lines describe an operation in one of the three formats above.

outputFormat

For each operation of type \(3\), output a single integer on a new line: the maximum \(b_y\) among all nodes meeting the conditions. If no valid node exists, output \(0\).

sample

3 2 3
1 2 3
1 2 3
1 2
1 3
3 1 1 3
1 1 2
3 1 1 1

3
2