arb

Se dă un arbore cu $N$ noduri numerotate de la $1$ la $N$, rădăcina fiind nodul cu numărul $1$.
Fiecare nod $i (1 \leq i \leq N)$ are asociată o valoare $C_i$.
Trebuie să răspundem la întrebări de tipul: „Care este suma valorilor asociate nodurilor din subarborele cu rădăcina în nodul $i$ aflate la distanţă cel mult egală cu $j$ faţă de nodul $i$?”.
Distanţa de la un nod $x$ la un nod $y$ este egală cu numărul de muchii de pe drumul de la $x$ la $y$.

Cerinţă

Să se scrie un program care să răspundă la $M$ întrebări de tipul specificat.

Date de intrare

Fişierul de intrare arb.in conţine pe prima linie numărul natural $N$. Pe a doua linie se află $N$ numere reprezentând costurile asociate celor $N$ noduri. Pe cea de a treia linie se află $N-1$ numere, cel de-al $i$-lea număr reprezentând părintele nodului cu numărul $i+1$. Pe a patra linie se află numărul natural $M$. Pe următoarele $M$ linii se află câte două numere naturale $i \ j$ reprezentând o întrebare de tipul specificat în enunţ ($i$ este rădăcina subarborelui, iar $j$ este distanţa maximă). Valorile aflate pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire arb.out va conţine $M$ linii. Linia $i$ conţine un singur număr natural reprezentând răspunsul la cea de a $i$-a întrebare din fişierul de intrare.

Restricții și precizări

• $1 \leq N \leq 250 \ 000$
• $1 \leq M \leq 500 \ 000$
• $0 \leq C_i \leq 5 \ 000$, $1 \leq i \leq N$

Exemplu

arb.in

7
1 2 2 1 3 4 5
1 1 1 3 3 6
3
3 1
3 2
1 0

arb.out

9
14
1