NOW I HAVE THE POWER ~ Victor, 2019

Victor, using the money he earned from selling horseshoe crabs, has managed to buy alien technology!

Using this alien technology, he terraforms Canada into a network of $N$ cities, numbered $1,2,\dots ,N$ connected by exactly $N-1$ highways. Victor lives in city $1$. He also hires $K$ aliens (numbered $1,2,\dots ,K$) to guard the cities with. As alien guards are expensive, each city has exactly $1$ guard assigned to it. An alien can be assigned to multiple cities, but can be present in at most one city at a time (thankfully, these aliens don't teleport).

Over the following $M$ minutes, one of the following happens:

• 1 c k: Alien $k$ is assigned to guard city $c$, replacing its previous alien guard.
• 2 u: The resistance plans a siege of city $u$ and wishes to know the maximum possible number of guards that can come reinforce city $u$.

As the head of intelligence at the resistance, you are tasked with writing a program to calculate these scenarios. A guard is able to reinforce city $u$ if and only if $u$ lies on the unique path between any one of its assigned cities and city $1$.

If only Victor hadn't been given the roll of paper of power…

Constraints

For all subtasks:

$1\le K\le N$

Subtask 1 [10%]

$1\le N,M\le 2000$

Subtask 2 [20%]

$1\le N,M\le 200000$

The alien guards are never reassigned.

Subtask 3 [40%]

$1\le N,M\le 200000$

Subtask 4 [30%]

$1\le N\le 500000$

$1\le M\le 300000$

Input Specification

The first line will contain three space-separated integers, $N$, $K$, and $M$.
The second line will contain $N$ space-separated integers, $c_1,c_2,\dots ,c_N$, indicating the $c_i$th alien is assigned to city $i$.
The next $N-1$ lines will each contain a pair of integers, $a_i,b_i$, indicating there is an edge between $a_i$ and $b_i$.
The next $M$ lines will each contain a query.

Output Specification

For each expedition, output the maximum possible number of guards that can come reinforce city $u$.

Sample Input 1

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

Sample Output 1

3
4
2
3

Sample Input 2

7 5 4
1 2 3 4 3 2 1
1 2
1 3
1 4
4 5
4 6
4 7
2 4
2 1
2 2
2 7

Sample Output 2

4
4
1
1