Reședința Larei a fost invadată de șobolani. Putem descrie reședința Lorei ca un arbore cu N noduri având rădăcina în nodul 1. Inițial niciun nod nu este infestat. Diverse evenimente se pot întâmpla pe rând, fiecare eveniment fiind de următoarele patru tipuri:

• 1 X – nodul X devine infestat
• 2 X – Lora vrea să elimine șobolanii din drumul de la nodul 1 la nodul X (inclusiv) folosind ultrasunete în toate nodurile simultan. Dacă se folosesc ultrasunete într-un nod infestat, șobolanii de acolo se împrăștie în toate nodurile vecine unde nu se folosesc ultrasunete, acestea devenind infestate. Nodurile unde se folosesc ultrasunete nu mai sunt infestate. După ce șobolanii au plecat, ultrasunetele se opresc, adică nodurile curățate vor putea fi infestate iar în evenimentele ulterioare.
• 3 X – Lora angajează profesioniști să curețe nodul X și fiii săi. Ca urmare, X și fiii direcți nu mai sunt infestați.
• 4 X – Lora ar vrea să știe numărul total de noduri infestate din subarborele cu rădăcina X.

Cerința

Ajutați-o pe Lora să scrie un program care prelucrează fiecare eveniment și determină răspunsurile la evenimentele de tip 4.

Date de intrare

Prima linie conține un singur întreg N – numărul de noduri din arbore. A doua linie conține N-1 numere, al i-lea fiind tatăl nodului i+1. Linia a treia conține numărul de evenimente Q. Următoarele Q linii conțin câte doi întregi reprezentând un eveniment în formatul descris anterior.

Date de ieșire

Pentru fiecare eveniment de tip 4 afișați o linie care conține un singur întreg – numărul de noduri infestate din subarbore.

Restricții și precizări

• 1 ≤ N, Q ≤ 300.000

Exemplu:

Intrare

5
1 1 3 3
8
1 3
2 5
4 1
1 1
2 1
4 3
3 1
4 3

Ieșire

1
2
1

Explicație

Evenimentele au următorul efect:

• 1 3 – Nodul 3 este infestat
• 2 5 – Lora folosește ultrasunete în nodurile din drumul de la 1 la 5. Acesteaa sunt 1, 3 și 5. Nodul 3 este infestat și singurul său vecin fără ultrasunete este 4. Astfel nodul 3 nu mai este infestat și 4 devine infestat.
• 4 1 – Subarborele cu rădăcina 1 conține toate nodurile. Singurul infestat este 4.
• 1 1 – Nodul 1 este infestat
• 2 1 – Lora folosește ultrasunete în nodul 1. Nodurile 2 și 3 devin infestate, iar nodul 1 nu mai este infestat.
• 4 3 – Subarborele cu rădăcina 3 conține nodurile 3, 4 și 5. Dintre ele 3 și 4 sunt infestate.
• 3 1 – Nodul 1 și fiii săi, adică nodurile 1, 2 și 3, nu mai sunt infestate.
• 4 3 – Dintre nodurile 3, 4 și 5, doar nodul 4 este infestat.