Fişierul intrare/ieşire:	prieteni2.in, prieteni2.out	Sursă	FMI No Stress 10
Autor	Stefan Radu	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.25 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Prieteni2

Moş Crăciun a vrut să facă un experiment anul acesta, aşa că a adunat n oameni şi i-a înşirat într-o linie. Se ştie că în această perioadă a anului se petrec trei tipuri de evenimente stranii.

• 1 i - omul i se împrieteneşte (ca prin minune) cu omul i + 1
• 2 i - omul i strică prietenia cu omul i + 1 (un comportament neînţeles)
• 3 a b - Moş Crăciun se întreabă care este cel mai lung şir de prieteni din intervalul [a, b]

Moş Crăciun a încercat să îşi răspundă la întrebări, dar bătrâneţea îşi spune cuvântul. În final vă cere vouă să îl ajutaţi.

Date de intrare

Fişierul de intrare prieteni2.in va conţine pe prima linie numărul n, iar pe a doua linie numărul q. Următoarele q linii vor descrie fiecare câte un eveniment.

Date de ieşire

Fişierul de ieşire prieteni2.out va conţine răspunsurile pentru evenimentele de tip 3, fiecare pe câte o linie.

Restricţii

• pentru 40% din punctaj 1 ≤ n, q ≤ 3000
• pentru alte 30% din punctaj 1 ≤ n, q ≤ 30000
• pentru alte 30% din punctaj 1 ≤ n, q ≤ 200000
• pentru evenimente de tip 1 se garantează că 1 ≤ i < n şi că i nu e prieten cu i + 1
• pentru evenimente de tip 2 se garantează că 1 ≤ i < n şi că i e prieten cu i + 1
• pentru evenimente de tip 3 se garantează că 1 ≤ a, b ≤ n

Exemplu

Explicaţie pentru exemplul 2

• 2 se împrieteneşte cu 3
• cel mai lung lanţ dintre 1 şi 3 este 2-3, de lungime 2
• 2 se supără cu 3
• cel mai lung lanţ dintre 2 şi 3 este de lungime 1 (doar 2, sau doar 3).

Cum se trimit solutii?