meet

În dimineața barajului $1$ de la lotul din Slatina, după ce s-au trezit la timp, campionii vor, bineînțeles, să servească micul dejun al campionilor. După cum știm cu toții, micul dejun al campionilor se ia numai la Profi.

Orașul Slatina poate fi privit ca un arbore cu $N$ noduri, fiecare nod fiind un punct de interes al orașului și unde punctele de interes sunt conectate între ele prin străzi bidirecționale de lungimi egale. Cum orașul Slatina este în continuă dezvoltare, în fiecare din următoarele $Q$ zile se va desfășura una din următoarele evenimente:

• în punctul de interes $u_i$ se va construi un magazin Profi. Este garantat că în punctul de interes $u_i$ nu era construit un magazin Profi.
• în punctul de interes $u_i$ se va demola magazinul Profi. Se garantează că în punctul de interes $u_i$ era construit un magazin Profi.

Deoarece campionii sunt indeciși cu privire la locația în care vor să servească micul dejun, ei vor să se întâlnească într-un punct de interes care este la distanță egală de toate magazinele Profi din oraș. Inițial, nu există niciun magazin Profi construit în oraș.

Cerință

Ajutați campionii să-și ia micul dejun! După fiecare dintre cele $Q$ zile calculați numărul de locații în care se pot întâlni campionii pentru a fi la distanță egală de toate magazinele Profi.

Date de intrare

Prima linie conține numerele $N$ și $Q$. Pe următoare linie se află $N$ numere, al $i$-lea reprezentând tatăl nodului $i$. Următoarele $Q$ linii conțin fiecare câte un număr întreg, $u_i$. Dacă $u_i > 0$, atunci se va construi un magazin Profi în punctul de interes $u_i$. Dacă $u_i < 0$, atunci se va demola magazinul Profi din punctul de interes $-u_i$.

Date de ieșire

Se vor afișa $Q$ linii. Pe a $i$-a linie se va afișa numărul de puncte de interes în care campionii se pot întâlni după ziua $i$, astfel încât să fie la distanță egală de toate magazinele Profi.

Restricții și precizări

• $1 \leq N, Q \leq 200 000$
• $0 \leq tată_i \leq N$
• Nodul cu $tată_i = 0$ este rădăcina arborelui.
• Se garantează faptul că șirul $tată$ descrie un arbore de mărime $N$.
• Se consideră că dacă nu există niciun Profi, atunci campionii se vor întâlni în orice punct de interes.
• $-N \leq u_i \leq N$ și $u_i \neq 0$, $\ \forall \ 1 \leq i \leq Q$.
• Distanța dintre două puncte de interes se consideră numărul de muchii dintre ele.
• Pentru $7$ puncte: $1 \leq N, Q\leq 200$
• Pentru $9$ puncte: $1 \leq N, Q \leq 2000$
• Pentru $20$ de puncte: $\sum_{i=1}^{Q} S_i \leq 1 000 000$, unde $S_i$ este numărul de magazine Profi din oraș la ziua $i$
• Pentru $8$ puncte: $u_i > 0$, $\ \forall \ 1 \leq i \leq Q$
• Pentru $56$ de puncte: Fără restricții suplimentare

Exemple

Exemplul 1

Intrare

7 3
6 7 2 6 3 0 4 
5
4
-5

Ieșire

7
1
7

Exemplul 2

Intrare

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

Ieșire

7
3
1
3
0
0
7
3
1
3
7
1