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 2\,000~

Subtask 2 [20%]

~1 \le N, M \le 200\,000~

The alien guards are never reassigned.

Subtask 3 [40%]

~1 \le N, M \le 200\,000~

Subtask 4 [30%]

~1 \le N \le 500\,000~

~1 \le M \le 300\,000~

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