Problem Description

The Kingdom of Paken consists of $ N $ cities numbered from $ 1 $ to $ N $ and $ N-1 $ roads connecting them. The $ i $-th road connects cities $ u_i $ and $ v_i $ bidirectionally and has a weight $ w_i $ which is an integer between $ 0 $ and $ 1 $ inclusive.

Now, Penguin-kun is going to travel through the Kingdom of Paken. Penguin-kun's journey is represented by $ M+1 $ integers $x_0, x_1, \ldots, x_M$, which indicate that Penguin-kun starts from city $ x_0 $ and visits cities $x_1, x_2, \ldots, x_M$ in this order (it is allowed to pass through other cities in between).

During the journey, Penguin-kun can repeat the following action as many times as he likes:

• Choose one city directly connected by a road to the city he is currently in, move to that city through the road. The cost is increased by the weight of the road traveled, and then the weight of that road (let's denote it as $ x $) is replaced by $ 1-x $.

Penguin-kun wants to minimize the total cost throughout the entire journey.

However, Penguin-kun is very fickle. Therefore, please process the following $ Q $ queries in the given order:

• Type 1: Given integers $ a $ and $ b $. Change $ x_a $ to $ b $.
• Type 2: Given integer $ r $. Calculate the minimum total cost when Penguin-kun starts from city $ x_0 $ and visits $x_1, x_2, \ldots, x_r$ in this order. Note that Type 2 queries are independent, so changes in edge weights during the movement are not considered for subsequent queries.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ Q $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $\hspace{0.8cm}\vdots$ $ u_{N-1} $ $ v_{N-1} $ $ w_{N-1} $ $ x_0 $ $ x_1 $ $\ldots$ $ x_M $ $\text{query}_1$ $\text{query}_2$ $\hspace{0.4cm}\vdots$ $\text{query}_Q$

Here, $\text{query}_i$ represents the content of the $ i $-th query, given in the following formats:

• If $\text{type}=1$, it indicates a Type 1 query, with the input format as follows:

$\text{type}$ $ a $ $ b $

• If $\text{type}=2$, it indicates a Type 2 query, with the input format as follows:

$\text{type}$ $ r $

Output Format

For each Type 2 query, output the value asked in the problem statement followed by a newline.

Sample Input and Output

Sample Input #1

3 3 3
1 2 0
1 3 1
1 3 2 3
2 2
1 2 1
2 3

Sample Output #1

1
2

Sample Input #2

5 10 8
1 2 0
3 1 0
2 4 0
5 4 1
1 3 4 2 5 3 1 3 4 2 4
1 2 1
1 6 2
2 5
1 6 4
2 9
2 8
1 7 1
2 2

Sample Output #2

4
9
8
1

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq u_i, v_i \leq N \ (1 \leq i \leq N-1)$
• $0 \leq w_i \leq 1 \ (1 \leq i \leq N-1)$
• $1 \leq x_i \leq N \ (0 \leq i \leq M)$
• For Type 1 queries, $0 \leq a \leq M, 1 \leq b \leq N$
• For Type 2 queries, $1 \leq r \leq M$
• $x_i \neq x_{i+1} \ (0 \leq i \leq M-1)$ holds before and after each query
• The $ Q $-th query is a Type 2 query
• The given graph is a tree
• All inputs are integers

Sample Explanation 1

For the first query, Penguin-kun should move in the order of vertex $1 \rightarrow$ vertex $3 \rightarrow$ vertex $1 \rightarrow$ vertex $ 2 $. The costs of the movements are $ 1 $, $ 0 $, $ 0 $ respectively, so the answer is $ 1 $. For the third query, Penguin-kun should move in the order of vertex $1 \rightarrow$ vertex $3 \rightarrow$ vertex $1 \rightarrow$ vertex $ 3 $. The costs of the movements are $ 1 $, $ 0 $, $ 1 $, $ 0 $ respectively, so the answer is $ 2 $.

Sample Explanation 2

Original idea: penguinman

见题面 Input 部分

见题面 Output 部分