J. Join the Joint
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Eva learned several advanced data structure techniques for trees. To show her progress, she asked Colin to give her a challenging problem about tree statistics.

However, Colin just gave her a very typical problem:

Given a tree with $$$n$$$ vertices, and vertex $$$1$$$ is the root. Each vertex has an integer weight $$$w_i$$$.

Let $$$lca(u,v)$$$ represent the lowest common ancestor of the vertices $$$u$$$ and $$$v$$$.

Given two integer sequences $$$a_1,a_2,\cdots,a_x~(1\le a_i\le n)$$$ and $$$b_1,b_2,\cdots,b_y~(1\le b_i\le n)$$$. Define the joint power of these two sequences to be $$$$$$ \sum_{i=1}^x\sum_{j=1}^yw_{lca(a_i,b_j)} $$$$$$

Please calculate the value of this joint power.

Eva thinks this problem is too easy, so she decided to change the problem into an online problem:

First, given the tree and the weight of each vertex. Initially, both sequences are empty.

Then there will be $$$m$$$ operations, each one is of the following two types:

  • 1 u : append $$$u~(1\le u\le n)$$$ to the end of the first sequence.
  • 2 u : append $$$u~(1\le u\le n)$$$ to the end of the second sequence.

After each operation, you need to output the current joint power of the two sequences.

However, this version of the problem is too hard for Eva, so she added an additional limitation that, after each operation, the sum of values in the first sequence will not exceed $$$10^6$$$. Now Eva turns this problem to you; do you know how to solve it?

Input

The first line contains two integers $$$n,m~(1\le n,m\le 10^5)$$$, representing the number of vertices in the tree and the number of operations.

The second line contains $$$n$$$ integers $$$w_1,w_2,\cdots,w_n(1\le w_i\le 10^5)$$$, representing the weight of each vertex.

For the following $$$n-1$$$ lines, each line contains two integers $$$u_i,v_i~(1\le u_i,v_i\le n, u_i\ne v_i)$$$, representing that there is an edge connecting $$$u_i$$$ and $$$v_i$$$ in the tree. It's guaranteed that all the edges in the input form a tree.

For the following $$$m$$$ lines, each line contains two integers $$$op_i, u_i~(op_i\in\{1,2\},1\le u_i\le n)$$$, representing an operation. It's guaranteed that after each operation, the sum of values in the first sequence will not exceed $$$10^6$$$.

Output

For each operation, output a single line with a single integer, representing the joint power of the two sequences after the corresponding operation.

Examples
Input
3 5
1 2 3
1 2
1 3
1 1
2 1
1 2
2 2
1 3
Output
0
1
2
5
7
Input
10 6
1 2 10 5 5 6 5 6 2 2
1 2
2 3
1 4
4 5
2 6
3 7
6 8
2 9
6 10
2 10
1 7
2 5
1 9
1 5
2 6
Output
0
2
3
6
12
17