Udalosti spomínané v tomto zadaní sú založené na pravdivých faktoch. Však si vyžiadaj vystúpenie, keď ho najbližšie stretneš.

Komu z nás sa nepáči mágia? Rýchle prsty, odvádzanie pozornosti a na prvý pohľad neuskutočniteľné veci? Niet divu, že aj Mišof sa v svojej mladosti naučil zopár trikov, ktoré teraz predvádza na skrátenie dlhej chvíle alebo na machrovanie v krčme.

Pozná pár kartových trikov, necháva miznúť zápalky a rôzne iné predmety, na povrazoch sa objavujú všelijaké uzly a dokonca dokáže opraviť roztrhnutú bankovku. Ako to robí? To ti, samozrejme, nemôžem povedať. Chápeš, tajomstvo kúzelníka.

Nedávno sa Mišof naučil nový trik a preto ti ho chcel predviesť. Do radu postavil $$n$$ nepriehľadných pohárov otočených hore dnom. Pod niektoré z nich položil guličku. Spýtal sa ťa na súvislý interval pohárov a začal odkrývať, čo sa nachádza pod nimi. Na tvoje prekvapenie pod každým z vybraných pohárov bolo presne to, čo si neočakával. Ak tam na začiatku gulička bola, teraz tam nie je a naopak. Uau. Potom guličky opäť zakryl a postup opakoval s novým intervalom. Si okúzlený?[^1]

“A to nie je všetko!” chváli sa Mišof. “Tiež ti viem ukázať najdlhšiu, nie nutne súvislú podpostupnosť pohárov, v ktorej sa pod pohármi najskôr guličky nenachádzajú a potom sa tam už stále nachádzajú.”

“Ale však to nie je ťažké.” Povieš a po chvíli premýšľania ukážeš správnu podpostupnosť.

“Áno? A dokážeš to, aj keď ti zmením tento interval, aj tento a nakoniec aj tento?” nedá pokoj Mišof.

No čo, dokážeš?

Úloha

Na vstupe dostaneš popis postupnosti a zmeny, ktoré nastali. Každá zmena je daná (uzavretým) intervalom pohárov. V tomto intervale sa objaví gulička pod každým pohárom, kde sa nenachádzala a zmizne spod každého pohára, kde bola. Jednotlivé zmeny na seba postupne naväzujú.

Raz za čas sa ťa Mišof opýta otázku: Aká je dĺžka najdlhšej (nesúvislej) podpostupnosti, kde na začiatku tejto podpostupnosti sú prázdne poháre a na konci poháre s guličkou? Presnejšie, po žiadnom pohári, pod ktorým je skrytá gulička nemôže v tejto podpostupnosti nasledovať pohár, pod ktorým gulička nie je.

Formát vstupu

V prvom riadku vstupu je číslo $$n$$ ($$1 \leq n \leq 300\,000$$) – počet pohárov v postupnosti.

V druhom riadku je reťazec znakov 0 a 1, kde 0 reprezentuje pohár, pod ktorým sa gulička nenachádza, a 1 reprezentuje pohár so skrytou guličkou. Tento reťazec určuje začiatočné rozmiestnenie guličiek.

V treťom riadku je číslo $$q$$ ($$1 \leq q \leq 300\,000$$) – počet udalostí.

Nasleduje $$q$$ riadkov popisujúcich jednotlivé udalosti. Ak sa v riadku nachádza iba jediný znak 1, znamená to, že Mišof sa pýta otázku na aktuálny stav pohárov a guličiek. Ak riadok začína znakom 2, znamená to zmenu intervalu, ktorý je definovaný nasledujúcimi dvoma číslami $$x_i$$ a $$y_i$$ ($$1 \leq x_i,y_i \leq n$$) na riadku. Prvé číslo je začiatok a druhé číslo je koniec daného intervalu.

Úloha má osem testovacích sád. V prvých piatich z nich platí, že $$n\cdot q \leq 1\,000\,000$$. Navyše, v každej párnej sade platí, že $$x_i=y_i$$.

Formát výstupu

Pre každú Mišofovu otázku, udalosť 1, vypíšte jedno číslo – dĺžku najdlhšej podpostupnosti pohárov, kde sa všetky poháre, pod ktorými nie je gulička, nachádzajú pred všetkými pohármi, pod ktorými gulička je.

Príklad

Input:

5
00001
6
1
2 1 2
1
2 1 1
2 4 4
1

Output:

5
3
4

V prvej otázke je správna odpoveď celá postupnosť. Po prvej zmene vyzerá celá postupnosť 11001. V tomto prípade jedna so správnych podpostupností pozostáva iba z jednotiek. Na konci dostaneme 01011 a do výsledku vyberiem obe nuly a posledné dve jednotky.

1. Tak stále buď, ale ak by ťa zaujímalo ako sa také niečo dá spraviť, odporúčam pozrieť www.youtube.com/watch?v=8osRaFTtgHo↩