Given a tree with $n$ nodes, each having a weight, the initial root is $1$.

There are $m$ operations of the following types:

1 x: Change the root of the tree to $x$.

2 x y: Given two nodes $x$ and $y$, consider every node in the subtree of $x$ and every node in the subtree of $y$. Calculate the number of pairs of nodes (one from each subtree) that have equal weights.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers, representing the weight $a_i$ of each node.

The next $n-1$ lines each contain two integers $x$ and $y$, representing an edge.

The next $m$ lines each represent an operation.

Output

For each query, output a single integer representing the answer.

Examples

Input 1

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

Output 1

0
1
1
1

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$, $1 \le a_i \le 10^9$.