Fișierul intrare/ieșire	burlane.in, burlane.out	Sursă	selecție lot Nerdvana 2024
Autor	codeforces	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.3 sec	Limită de memorie	524288 KB
Scorul tău	N/A	Dificultate	1.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Burlane

Notă: această problemă este similară cu Holes.

O clădire are N + 1 etaje numerotate de la 0 la N (considerăm că parterul este etajul 0). Pentru colectarea apei de ploaie, de la fiecare etaj i ≥ 1 pornește cîte un burlan care coboară pînă la etajul p_i, unde 0 ≤ p_i < i. Un burlan care ajunge la un etaj se deversează în burlanul care pornește de la acel etaj. Astfel, apa de ploaie de la orice etaj ajunge invariabil la parter, trecînd prin unul sau mai multe burlane.

Dorim să procesăm Q operații, care pot fi de două tipuri:

1. Turnăm apă în burlanul care pornește de la etajul x (0 < x ≤ N).
2. Înlocuim burlanul care pornește de la etajul x (0 < x ≤ N) cu unul care duce pînă la etajul y. În continuare se garantează că 0 ≤ y < x.

Pentru fiecare operație de tipul 1, aflați prin cîte burlane trece apa pînă ajunge la parter.

Date de intrare

Fișierul de intrare burlane.in conține pe prima linie numerele N și Q, separate prin spațiu. A doua linie conține valorile inițiale p₁, p₂, ..., p_N, separate prin spații. Următoarele Q linii conțin operațiile sub una dintre formele:

• 1 x pentru operații de tipul 1;
• 2 x y pentru operații de tipul 2.

Date de ieșire

În fișierul de ieșire burlane.out afișați răspunsurile la operațiile de tipul 1, cîte unul pe linie.

Restricții

• 1 ≤ N ≤ 100.000
• 1 ≤ Q ≤ 100.000

Exemplu

Explicație

Traseele apei sînt:

• 6 → 4 → 2 → 1 → 0;
• 3 → 0;
• 7 → 3 → 0;
• 6 → 5 → 3 → 2 → 1 → 0.