Secret Base

설곽국 is a country with N cities numbered from 1 to $N$. There are $N-1$ roads connecting pairs of cities, and all cities are connected. Every road has length $1$.

One day, the neighboring country 경곽국 announced an invasion through a news report. The nervous people of 설곽국 decided to build a secret base. The base is built temporarily and simply, so it can be moved easily.

The base is built in a city that satisfies the following property.

• If the base is built in city $x$, define $f(x)=\sum_{i=1}^n A_i \times \text{dist}(i, x)$ as the sum of the travel distances of all people to city $x$. Here $\text{dist}(x, y)$ is the distance between city $x$ and city $y$.
• The base is built in a city $x$ where $f(x)$ is minimal among all cities. If several cities qualify, the base can be built in any of them.

Brue, who lives in 설곽국, wants to know the total travel distance of the people after building the base.

Over time, the number of people in a city changes exactly $Q$ times. After each change, the total travel distance may change, and the base may move as a result. Find the total travel distance for every time point.

The first line contains the number of cities $N$ and the number of changes $Q$.

The second line contains the number of people in each city $A_1$, $A_2$, $\cdots$, $A_N$, separated by spaces.

From the third line, the next $N-1$ lines describe the road structure of 설곽국. The $i$-th line contains two integers $x_i$ and $y_i$, meaning that road $i$ connects city $x_i$ and city $y_i$.

From line $N+2$, the next $Q$ lines describe the changes as $v_i$ $d_i$. This means the number of people in city $v_i$ becomes $d_i$.

Print $Q+1$ lines. The first line is the total travel distance to the base in the initial state, and each of the next $Q$ lines is the total travel distance after each population change.

• $2 \le N \le 2 \times 10^5$
• $2 \le Q \le 2 \times 10^5$
• $1 \le A_i \le 10^6$ ($1 \le i \le N$)
• $1 \le x_i \le N$
• $1 \le y_i \le N$
• The input is guaranteed to be a valid tree.
• $1 \le v_i \le N$ ($1 \le i \le Q$)
• $1 \le d_i \le 10^6$ ($1 \le i \le Q$)

The distance between two cities $a$ and $b$ is the number of roads on the shortest path from city $a$ to city $b$.