arb

Se dă un arbore cu $n$ noduri numerotate de la $1$ la $n$ şi rădăcina nodul $1$, în care fiecare nod are asociată o valoare distinctă. Pe acest arbore se fac un număr infinit de drumuri: se pleacă din nodul rădăcină şi la fiecare pas, pentru nodul curent se alege fiul cu valoarea cea mai mare până se ajunge la o frunză. Odată parcurs un nod, acestuia îi scade valoarea cu o unitate. Dacă la un moment dat sunt doi fii cu aceeaşi valoare, se alege cel care iniţial a avut valoarea mai mare. Mai mult, se garantează că înălţimea arborelui este mai mică sau egală cu $20$.

Cerință

Să se răspundă la întrebări de forma $(x,y)$ având următoarea semnificaţie: după câte astfel de drumuri nodul $x$ va fi parcurs de exact $y$ ori? (adică drumul la care nodul $x$ a fost accesat a $y$-a oară)

Date de intrare

Fişierul de intrare arb.in conţine pe prima linie două numere naturale $n$ şi $q$ despărţite printr-un spaţiu, ce reprezintă, în ordine, numărul de noduri al arborelui şi numărul de întrebări. A doua linie a fişierului conţine $n-1$ numere naturale despărţite prin câte un spaţiu. Al $i$-lea număr de pe această linie reprezintă părintele nodului cu indicele $i+1$. Pe a treia linie se află $n$ numere naturale despărţite prin câte un spaţiu reprezentând valorile celor $n$ noduri în ordinea crescătoare a indicilor. Următoarele $q$ linii conţin câte două numere naturale $x$ şi $y$ separate printr-un spaţiu: nodul de interes, respectiv numărul de accesări al acestuia.

Date de ieșire

Fişierul de ieşire arb.out va conţine $q$ linii reprezentând răspunsul fiecărei întrebări.

Restricții și precizări

• $2 ≤ n , q ≤ 100\ 000$
• Valorile din noduri sunt numere naturale mai mici sau egale cu $1 \ 000 \ 000 \ 000$.
• Pentru fiecare întrebare răspunsul se reprezintă pe 32 de biţi cu semn.
• Înălţimea arborelui este mai mică sau egală decât $20$.

Exemplu

arb.in

5 3
1 1 3 3
10 7 5 2 3
4 2
5 3
3 1

arb.out

12
10
4