Candy Selling in the Markets

In a city there are N markets connected by N-1 roads forming a tree. Each market has two attributes: a skill value and a difficulty.

Sandu starts each day at market 1 with an initial skill of 0. When he visits a market, his current skill increases by that market's skill value. Immediately after arriving, if his updated skill is at least the market's difficulty, he is able to sell candy at that market.

Initially, every market's skill value is 0. Over the next Q days, there are events. On the j-th day an event is given as two integers u_j and x_j meaning that the skill value of market u_j increases permanently by x_j.

After processing the event for a day, Sandu again starts at market 1 with a skill of 0. He then chooses an arbitrary market k and travels along the unique path from market 1 to market k (including both endpoints). Along this path, his skill accumulates as described and at each market he tries to sell candy (if his current skill is at least that market's difficulty, the sale is successful). Note that he always visits all markets on the path even if a sale in some market fails.

Your task is to determine, for each day, the maximum number of markets on some path from market 1 at which Sandu can successfully sell candy.

Note: The input describes a tree and a sequence of update events. The difficulty values for the markets are fixed and provided in the input.

The formulas must use LaTeX format. For example, the number of markets is given by $N$, and there are $N-1$ roads. When visiting a market $i$, if the cumulative skill $S$ satisfies $S \geq d_i$ (where $d_i$ is the difficulty of market $i$), then the sale is successful.

inputFormat

The input begins with two integers N and Q ($1 \leq N, Q \leq 10^5$), denoting the number of markets and the number of days (events) respectively.

Then follow N-1 lines, each containing two integers u and v, indicating an undirected road connecting market u and market v.

The next line contains N integers, where the i-th integer denotes the difficulty $d_i$ of market i.

Then follow Q lines, each containing two integers u_j and x_j, meaning that on day j the skill value of market u_j increases by x_j.

outputFormat

Output Q lines. The j-th line should contain a single integer, which is the maximum number of markets at which Sandu can successfully sell candy on day j after applying the update of that day.

sample

3 2
1 2
1 3
0 5 3
2 5
3 10

2
2