You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Initially, there is a single integer written on every vertex: the vertex $$$i$$$ has $$$p_i$$$ written on it.
You have to process $$$q$$$ queries of three types:
- $$$1$$$ $$$i$$$ — delete the $$$i$$$-th edge from the graph.
- $$$2$$$ $$$u$$$ $$$x$$$ — change the value of $$$p_u$$$ to x, i.e. $$$p_u := x$$$.
- $$$3$$$ $$$v$$$ — among all vertices reachable from the vertex $$$v$$$ using the edges of the graph(including the vertex $$$v$$$ itself), find a vertex $$$u$$$ with the largest number $$$p_u$$$ written on it, print $$$p_u$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^{5})$$$ — the number of vertices of the graph and the number of edges of the graph.
The second line contains $$$n$$$ space-separated integers $$$p_1, p_2, \ldots, p_n$$$ — $$$p_i$$$ is the number initially written on vertex $$$i(1 \le p_i \le 10^9)$$$.
Then $$$m$$$ lines follow, the $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le n, a_i \neq b_i)$$$ and means that the $$$i$$$-th edge connects vertices $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the graph does not contain multi-edges.
The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.
The $$$q$$$ lines follow, which describe the queries. Each line is given by one of the following formats:
- $$$1$$$ $$$i$$$ — denotes a query of the first type with an edge $$$i$$$ $$$(1 \le i \le m)$$$. For each query of the first type, it is guaranteed that the corresponding edge is not deleted from the graph yet.
- $$$2$$$ $$$u$$$ $$$x$$$ — denotes a query of the second type, with a vertex $$$u(1 \le u \le n)$$$ and a value $$$x(1 \le x \le 10^9)$$$.
- $$$3$$$ $$$v$$$ — denotes a query of the third type, with a vertex $$$v(1 \le v \le n)$$$.
For every query of the third type, print the value of $$$p_u$$$ written on the chosen vertex $$$u$$$.
7 6 4 7 3 4 3 2 1 1 2 1 5 2 4 2 5 3 6 3 7 6 3 1 1 1 1 2 3 1 2 7 10 3 3
7 4 10
In the 1st test, the initial graph is,
For the 1st query, vertex 1,2,4,5 are reachable from vertex-1 and the largest value is 7, written on vertex-2.
For the 2nd and 3rd queries, we delete the 1st, and 2nd edge. Then the updated graph is,
In the 4th query, the largest value is 4 found on vertex-1, which is the only node reachable from vertex-1.
In the 5th query, the updated value of vertex-6 is 10.
In the 6th query, the largest value is 10 found on vertex-6.
