Satul Mirşid este format din N case numerotate cu numerele naturale de la 1 la N. În casa numerotată cu 1 se află un generator care alimentează cu curent electric toate casele din sat astfel: casa cu numărul 1 alimentează cu curent un număr de case, fiecare dintre aceste case alimentând la rândul lor alte case, ş.a.m.d. Fiecare casă este alimentată de exact o sursă de curent (care poate fi o altă casă alimentată cu curent electric sau generatorul, în cazul casei cu numărul 1). În fiecare casă există o singură siguranţă electrică. În cazul unei defecţiuni la un aparat electric dintr-o casă, siguranţa casei se arde. În acest caz, alimentarea cu curent electric a casei se întrerupe, determinând întreruperea curentului în toate casele alimentate de la aceasta, direct sau indirect.
Compania producătoare de siguranţe are un jurnal în care a fost notată fiecare zi în care s-a ars, respectiv s-a înlocuit, o siguranţă, împreună cu numărul casei în care s-a petrecut evenimentul. Jurnalul conţine în total M evenimente. Pentru a stabili gradul de mulţumire al clienţilor, compania vrea să afle numărul total de case care aveau curent electric în anumite zile de interes.
Cerinţă
Să se scrie un program care să determine numărul de case care aveau curent electric pentru fiecare dintre zilele de interes stabilite de conducerea companiei.
Date de intrare
Fişierul de intrare curent.in are pe prima linie numărul natural N. A doua linie, conţine N-1 numere naturale nenule cel mult egale cu N, separate prin câte un singur spaţiu, cel de al k-lea număr (1≤k<N) reprezentând numărul casei de la care primeşte curent casa cu numărul k+1. A treia linie conţine un număr natural M reprezentând numărul de evenimente notate în jurnalul companiei. Fiecare dintre următoarele M linii conţin, câte 3 numere naturale a b c , separate prin câte un spaţiu, care descriu astfel un eveniment: dacă c este 0 atunci în ziua a s-a ars siguranţa în casa b , daca c este 1 atunci în ziua a s-a înlocuit siguranţa din casa b . Linia M+4 a fişierului conţine un număr natural T reprezentând numărul zilelor pentru care trebuie determinat numărul caselor ce au curent electric, iar linia M+5 a fişierului conţine un şir strict crescător de T numere naturale, separate prin câte un spaţiu, reprezentând zilele de interes stabilite de conducerea companiei. Zilele sunt numerotate de la 1 la 109.
Date de ieşire
Fişierul de ieşire curent.out va contine T linii, fiecare linie k (1≤k≤T) va conţine un număr natural reprezentând numărul de case care aveau curent electric în a k-a zi de interes (în ordinea din fişierul de intrare).
Restricţii
0 < N < 100011
0 < M < 100022
0 < T < 100033
Dacă a b c şi a’ b’ c’ sunt valorile care descriu, în fişierul de intrare, două evenimente, iar a=a’ atunci b≠b’
În ziua 2, siguranţa din casa 3 se arde, casele 3,4,5,6,7,8 nemaifiind alimentate cu curent electric. Siguranţa nu a fost înlocuită până în ziua 8, rămânând doar 5 case alimentate (1,2,9,10,11), valoarea 5 scriidu-se pe prima linie a fişierului curent.out. În zilele 9 şi 10 se ard siguranţele din casele 9 şi 10. Astfel, în ziua 13 doar 2 case (1 şi 2) sunt alimentate cu curent, valoarea 2 scriidu-se pe a doua linie a fişierului.
În ziua 14 se arde siguranţa din casa 5 fapt care nu modifică numărul caselor alimentate cu curent. În ziua 22 se repară siguranţa în casa 3, în ziua 23 fiind 5 case alimentate cu curent (1,2,3,4,6), valoarea 5 scriidu-se pe a treia linie a fişierului.
În ziua 31 se arde siguranţa din casa 1, astfel că în ziua 33 nicio casă nu mai este alimentată cu curent, valoarea 0 scriindu-se pe cea de-a patra linie a fişierului.