You are given a tree with $n$ nodes, where each node has a color. There are $m$ updates. After each update, you need to output the sum of the number of distinct colors on all directed simple paths in the tree.

Input

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

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq n$), where $c_i$ is the initial color of node $i$.

The next $n-1$ lines each contain two integers $u, v$ ($1 \leq u, v \leq n$), representing an edge between $u$ and $v$.

The following $m$ lines each contain two integers $u, x$ ($1 \leq u, x \leq n$), indicating that the color of node $u$ is changed to $x$.

Output

Output $m+1$ lines, each containing an integer representing the sum of the number of distinct colors on all directed simple paths in the tree, initially and after each update.

Constraints

For $100\%$ of the data, $2 \leq n \leq 4 \times 10^5$ and $1 \leq m \leq 4 \times 10^5$.

Examples

Input 1

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

Output 1

47
51
49
45

Input 2

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

Output 2

36
46

Note

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