사탕 판매

Sandu는 고등학교를 졸업하고 사탕 판매원으로서 자신의 열정을 좇기로 했다.

몰도바의 도시 Balti에는 도로로 연결된 $N$개의 시장이 있다. 어떤 시장에서든 도로를 따라 다른 모든 시장으로 이동할 수 있고, 도로는 정확히 $N - 1$개이다. Sandu는 시장 $1$에 있으므로, 시장들은 시장 $1$을 루트로 하는 트리를 이룬다.

각 시장 $i$에는 요구 수준 $t_i$와 학습 수준 $l_i$가 있다. 처음에는 모든 시장의 학습 수준이 $0$이고, Sandu의 판매 기술 수준은 $0$이다.

Sandu가 시장 $i$를 방문하면 판매 기술 수준이 $l_i$만큼 오른다. 판매 기술 수준이 $t_i$ 이상이면 시장 $i$에서 성공한다. 기술 수준은 시장 $i$에 들어가는 순간 오르므로, 판매를 시도하기 전에 이미 반영되어 있다.

$j$일마다 두 양의 정수 $u_j$, $x_j$로 주어지는 사건이 일어난다. 시장 $u_j$의 학습 수준이 $x_j$만큼 영구히 증가한다 ($l_{u_j} := l_{u_j} + x_j$).

매일 Sandu는 최종 시장 $k$를 고르고, 시장 $1$에서 $k$까지의 경로에 있는 모든 시장을 그 순서대로 방문한다. 성공 여부와 상관없이 $k$까지 계속 나아간다. 매일 Sandu는 판매 기술 수준 $0$으로 시장 $1$에서 출발한다.

각 날 $j$에 대해, 그날의 최종 시장을 최적으로 골랐을 때 Sandu가 성공할 수 있는 시장 수의 최댓값을 구하라.

첫 줄에 두 정수 $N$, $Q$ ($1 \le N, Q \le 5 \cdot 10^5$)가 주어진다.

둘째 줄에는 $N - 1$개의 정수 $p_2, \dots, p_N$이 주어진다. $p_i$와 $i$ 사이에 간선이 있고, $p_i$는 $i$의 부모이다. 항상 $1 \le p_i < i$이다.

셋째 줄에는 $N$개의 정수 $t_1, t_2, \dots, t_N$ ($0 \le t_i \le 10^9$)이 주어진다.

이어지는 $Q$개의 줄에는 $j$일의 사건을 나타내는 두 정수 $u_j$, $x_j$ ($1 \le u_j \le N$, $1 \le x_j \le 10^9$)가 한 줄에 하나씩 주어진다.

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$일의 답을 출력한다.

• 모든 $i$에 대해 $1 \le p_i < i$이다.
• 모든 $i$ ($1 \le i \le N$)에 대해 $0 \le t_i \le 10^9$이다.
• 모든 $j$ ($1 \le j \le Q$)에 대해 $1 \le u_j \le N$이다.
• 모든 $j$ ($1 \le j \le Q$)에 대해 $1 \le x_j \le 10^9$이다.