Kelian is a girl who loves reading.

Recently, she read a very interesting novel, and the fictional world in this novel piqued her interest.

This world has $n$ cities, and these $n$ cities are connected by exactly $n - 1$ bidirectional roads, meaning any two cities can reach each other. At the same time, city 1 is located at the center of the world; occupying this city means dominating the world.

Initially, none of the $n$ cities are under the control of any country. However, as society develops, some cities rise to form countries and seize hegemony over the world. For convenience, we label the country formed by the rise of city $i$ as country $i$. During the process of city $i$ rising, country $i$ gains control over all cities on the path from city $i$ to city 1.

The rise of a new city often implies war and death. If country $i$ is rising and needs to gain control of a city that was originally controlled by country $j$ ($j \neq i$), then country $i$ must declare war on country $j$ and engage in conflict.

Now, Kelian knows that in history, city $i$ rose a total of $a_i$ times. However, the relative order of these events is no longer traceable. The only information available is that before a city rises to dominate the world, no new city will rise.

War is catastrophic for the people. Kelian defines the "disaster level" of a rise as the number of different countries it goes to war with during the process (going to war with the same country multiple times is only counted once). Kelian wants to know, among all possible rise sequences, what is the maximum sum of disaster levels.

Meanwhile, thanks to the efforts of archaeologists, more and more historical data has been unearthed. Based on this new information, Kelian will make some adjustments to $a_i$. Specifically, Kelian will perform some operations, each time adding $w$ to $a_x$. She hopes to calculate the maximum disaster level after each modification.

However, Kelian is not interested in complex calculations, so she wants you to help her calculate these values.

Supplementary notes on the problem: Countries formed by the same city rising multiple times are the same country, which means that if the same city rises twice consecutively, it will not go to war with any country, because these cities were already under its control. In the course of historical evolution, country $i$ may have a period where it does not control any cities. But this does not mean that country $i$ has perished; when city $i$ rises, country $i$ will still gain control of the cities on the path from 1 to $i$.

Input

The first line contains two integers $n$ and $m$, representing the number of cities and the number of operations. The second line contains $n$ integers representing the initial values of $a_i$. The next $n - 1$ lines each contain two integers $u_i, v_i$ ($1 \le u_i, v_i \le n$), describing a road. The next $m$ lines each contain two integers $x_i, w_i$, representing adding $w_i$ to $a_{x_i}$.

Output

Output a total of $m + 1$ lines. The first line represents the answer for the initial $a_i$, and the next $m$ lines each represent the answer after that modification.

Examples

Input 1

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

Output 1

6
7
9
10

Note

Before the modifications begin, if the cities rise in the order 4, 1, 5, 3, 2, then they will sequentially go to war with 0, 1, 2, 1, 2 countries respectively. This results in a total of 6 hostile relationships. It can be proven that this is the maximum value among all possible rise sequences.

Constraints

For 100% of the data, $1 \le a_i, w_i \le 10^7$, $1 \le x_i \le n$.