J. k-MEX
time limit per test
5 s
memory limit per test
256 MB
input
standard input
output
standard output

Kagari is managing a finished world tree. The tree is rooted at a specific vertex $$$r$$$, and each vertex has an integer value. To process the tree more efficiently, she may do the following operation on an arbitrary vertex $$$v$$$ ($$$v \neq r$$$):

  1. Let the path from vertex $$$r$$$ to vertex $$$v$$$ consist of the sequence of vertices $$$u_1, u_2, \dots, u_m$$$, where $$$u_1=r$$$ and $$$u_m=v$$$.
  2. Remove the edges $$$(u_1, u_2), (u_2, u_3), \dots, (u_{m-1}, u_m)$$$.
  3. Connect vertex $$$r$$$ with $$$u_2, u_3, \dots, u_m$$$ directly.

During this process, Kagari may also query the $$$k$$$-MEX$$$^{\text{∗}}$$$ value of the set of vertex integer values in a given subtree$$$^{\text{†}}$$$. Can you help her program to answer her queries efficiently?

$$$^{\text{∗}}$$$The $$$k$$$-th minimum excluded ($$$k$$$-MEX) of a collection of integers $$$c_1, c_2, \ldots, c_n$$$ is defined as the $$$k$$$-th smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

$$$^{\text{†}}$$$A vertex $$$u$$$ is said to be in the subtree of vertex $$$v$$$ if and only if the path from $$$u$$$ to the root contains $$$v$$$.

Input

The first line of each test contains three integers $$$n$$$, $$$q$$$, and $$$r$$$ ($$$1 \le n, q \le 10^6$$$, $$$1 \le r \le n$$$) — the size of the tree, the number of queries and operations, and the root vertex.

The second line of each test contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_i\le n$$$) — the integer values of each vertex.

The following $$$n-1$$$ lines of each test describe the tree. Each of the lines contains two integers $$$u$$$ and $$$v$$$ that indicate an edge between vertex $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree.

The following $$$q$$$ lines of each test describe the queries and operations. Each of the lines is either of:

  • $$$1$$$ $$$v$$$ ($$$1 \le v \le n, v \neq r$$$) that indicates an operation on vertex $$$v$$$.
  • $$$2$$$ $$$v$$$ $$$k$$$ ($$$1 \le v \le n$$$, $$$1 \le k \le 10$$$) that indicates a $$$k$$$-MEX query of the subtree of vertex $$$v$$$.
Output

For each $$$k$$$-MEX query, output an integer — the answer to that query.

Example
Input
11 6 1
4 5 6 0 2 1 8 2 3 0 4
1 2
1 3
2 4
3 5
3 8
5 6
5 7
7 9
7 10
5 11
2 3 1
1 7
2 5 3
2 4 2
1 9
2 1 2
Output
5
5
2
9
Note

The initial tree is shown in the figure below.

In the first query, the values of the subtree of vertex $$$3$$$ are $$$[6,2,1,8,2,3,0,4]$$$, and its $$$1$$$-MEX is $$$5$$$.

After the operation on vertex $$$7$$$, the tree is shown in the figure below.

In the second query, the values of the subtree of vertex $$$5$$$ are $$$[2,1,4]$$$, and its $$$3$$$-MEX is $$$5$$$.

In the third query, the values of the subtree of vertex $$$4$$$ are $$$[0]$$$, and its $$$2$$$-MEX is $$$2$$$.

After the operation on vertex $$$9$$$, the tree is shown in the figure below.

In the fourth query, the values of the subtree of vertex $$$1$$$ are $$$[4,5,6,0,2,1,8,2,3,0,4]$$$, and its $$$2$$$-MEX is $$$9$$$.