Sweets

Sandu graduated from high school and decided to pursue his passion as a candy salesperson.

Balti, a city in Moldova, has $N$ markets connected by streets. Any market can be reached from any other market by traveling through some streets, and there are exactly $N - 1$ streets. Sandu is at market $1$, so the markets form a tree rooted at market $1$.

Each market $i$ has a toughness level $t_i$ and a learning level $l_i$. Initially every learning level is $0$, and Sandu's selling skill level is $0$.

When Sandu visits market $i$, his selling skill level increases by $l_i$. He succeeds at market $i$ if his selling skill level is at least $t_i$. The skill level increases as soon as he enters market $i$, before he tries to sell anything there.

Each day $j$ has an event with two positive integers $u_j$ and $x_j$. The learning level of market $u_j$ permanently increases by $x_j$ ($l_{u_j} := l_{u_j} + x_j$).

Each day Sandu picks a final market $k$ and visits every market on the path from market $1$ to market $k$, in that order. He keeps going to $k$ whether or not he succeeds. Every day he starts at market $1$ with a selling skill level of $0$.

For each day $j$, find the largest number of markets where Sandu can succeed if he picks the final market of that day optimally.

The first line contains two integers $N$ and $Q$ ($1 \le N, Q \le 5 \cdot 10^5$).

The second line contains $N - 1$ integers $p_2, \dots, p_N$. There is an edge between $p_i$ and $i$, and $p_i$ is the parent of $i$. It is always true that $1 \le p_i < i$.

The third line contains $N$ integers $t_1, t_2, \dots, t_N$ ($0 \le t_i \le 10^9$).

Each of the next $Q$ lines contains two integers $u_j$ and $x_j$ ($1 \le u_j \le N$, $1 \le x_j \le 10^9$) describing the event on day $j$.

Output $Q$ lines. The $j$-th line contains the answer for day $j$.

• $1 \le p_i < i$ for all $i$.
• $0 \le t_i \le 10^9$ for all $i$ ($1 \le i \le N$).
• $1 \le u_j \le N$ for all $j$ ($1 \le j \le Q$).
• $1 \le x_j \le 10^9$ for all $j$ ($1 \le j \le Q$).