impiedicat

Gimi guguștiucul a intrat din nou în belele, el vizitează un oraș sub formă de arbore cu $N$ intersecții, conectate între ele prin $N - 1$ străzi bidirecționale înrădăcinat în intersecția cu indicele $1$. Intersecțiile orașului sunt numerotate de la $1$ la $N$, iar pentru fiecare intersecție $i$ se cunosc $p_i$, intersecția părinte a intersecției $i$ și $d_i$, dimensiunea unui monument din intersecție.

Cerință

Pe parcurs ce Gimi vizitează orașul, acesta va face $Q$ zboruri plecând de la o intersecție $x$, câtre o intersecție $y$, vizitând toate intersecțiile de pe lanțul de la $x$ la $y$ în ordine. Cum guguștiucul nostru este foarte împiedicat acesta se va lovi de fiecare monument mai mare sau egal decât toate monumentele din intersecțiile vizitate până atunci de pe lanț. Astfel, guguștiucul se va lovi inclusiv de monumentul din intersecția $x$ din care pleacă.

Gimi vrea să știe pentru fiecare zbor din cele $Q$ de câte monumente se va lovi.

Date de intrare

Pe prima linie a fişierului de intrare se află două numere $N$ și $Q$, reprezentând numărul de intersecții, respectiv numărul de zboruri pe care Gimi le va efectua. Pe a doua linie se află $N$ numere reprezentând șirul $d_1, d_2, \ldots, d_n$. Pe a treia linie, se află $N-1$ valori reprezentând șirul $p_2, p_3, \dots, p_n$. Pe următoarele $Q$ linii se află câte două numere $x_i$, $y_i$ ce descriu a $i$-a întrebare.

Date de ieșire

În fişierul de ieşire se vor afla $Q$ numere, fiecare pe câte o linie. Al $i$-lea număr reprezintă raspunsul la cea de-a $i$-a întrebare.

Restricții și precizări

• $1\leq N \leq 200\ 000$
• $1\leq Q \leq 200\ 000$
• $1\leq p_{i} \leq N$
• $1\leq d_{i} \leq N$
• Nodul $1$ nu are părinte.

Exemplu

impiedicat.in

8 9
3 2 4 1 3 1 2 1
1 1 2 2 4 5 1
6 8
8 6
6 7
7 6
6 1
1 6
4 5
5 4
6 3

impiedicat.out

4
2
4
2
4
1
3
1
5

Explicație

Dimensiunile monumentelor vizitate pentru fiecare zbor sunt:

• $\textcolor{red}{1} \rightarrow \textcolor{red}{1} \rightarrow \textcolor{red}{2} \rightarrow \textcolor{red}{3} \rightarrow 1$
• $\textcolor{red}{1} \rightarrow \textcolor{red}{3} \rightarrow 2 \rightarrow 1 \rightarrow 1$
• $\textcolor{red}{1} \rightarrow \textcolor{red}{1} \rightarrow \textcolor{red}{2} \rightarrow \textcolor{red}{3} \rightarrow 2$
• $\textcolor{red}{2} \rightarrow \textcolor{red}{3} \rightarrow 2 \rightarrow 1 \rightarrow 1$
• $\textcolor{red}{1} \rightarrow \textcolor{red}{1} \rightarrow \textcolor{red}{2} \rightarrow \textcolor{red}{3}$
• $\textcolor{red}{3} \rightarrow 2 \rightarrow 1 \rightarrow 1$
• $\textcolor{red}{1} \rightarrow \textcolor{red}{2} \rightarrow \textcolor{red}{3}$
• $\textcolor{red}{3} \rightarrow 2 \rightarrow 1$
• $\textcolor{red}{1} \rightarrow \textcolor{red}{1} \rightarrow \textcolor{red}{2} \rightarrow \textcolor{red}{3} \rightarrow \textcolor{red}{4}$

Cu $\textcolor{red}{roșu}$ s-au marcat monumentele de care Gimi se lovește în timpul zborului.