Zenit

Zadanie

Gooooooool

Počet bodov: 50

Meky Žbirka žiaľ neuspel v získaní novej krásnej tváre, ale našťastie má ešte zopár nedokonalostí v rukáve (doslova), na ktoré sa vie sústrediť. Keďže v Šamoríne sa oteplieva a začína tielková sezóna, obzvlášť ťažko znáša svoje krivé ruky. Z chýb sa síce treba poučiť, ale nikto nepovedal, že hneď na prvý šup. A presne preto Vám predstavujeme skvelý nový turnaj Mekyho Žbirku vo vajcohode!

Turnaja sa zúčastnilo \(2^n\) tímov a odohrali klasického pavúka kým nezostal 1 víťaz. Meky nemá čas strácať čas, a tak priebeh turnaja nechal v rukách svojich neschopných pomocníkov. Problém však je, že títo boli naozaj neschopní a zápis z turnaja neobsahoval kompletné informácie.

Avšak aj z nekompletného zápisu, vieme zistiť, koľko tímov mohlo potenciálne turnaj vyhrať. Meky by si teda mohol aspoň jednoducho spočítať, koľko má potenciálnych víťazných tímov. V tom však jeho neschopní pomocníci začali zmätkovať a meniť niektoré zápisy (Mekyho sklamaný výraz ich vystrašil. No pravdu povediac, hocijaký Mekyho výraz je od incidentu v Patinciach strašidelný.).

Meky si pre istotu povedal, že treba vypočítať počet potenciálnych víťazných tímov po každej zmene. Samozrejme, nebude to robiť on sám a jeho neschopní pomocníci už narobili škody dosť. Chcelo by to pre zmenu nejakých šikovných pomocníkov. Skúste sa mu ponúknuť, dá vam za to body do Zenitu.

Úloha

\(2^n\) tímov odohralo \(2^n - 1\) hier. Na začiatku boli tímy rozdelené do párov. V prvej hre proti sebe hrali tím 1 a tím 2. V druhej hre proti sebe hrali tím 3 a tím 4. A tak ďalej. Keď všetky dvojice odohrali svoje zápasy, v ďalšom kole proti sebe hrali víťazi prvej hry proti víťazom druhej hry. Potom hrali víťazi tretej hry proti víťazom štvrtej hry. Tento princíp sa opakuje, až pokým neskončíme s jediným víťazným tímom.

Výsledky turnaja sú chronologicky reprezentované reťazcom \(s\) dĺžky \(2^n - 1\) nasledujúcim spôsobom:

ak je \(s_i\) rovné \(0\), hru číslo \(i\) vyhral tím s nižším indexom;
ak je \(s_i\) rovné \(1\), hru číslo \(i\) vyhral tím s vyšším indexom;
ak je \(s_i\) rovné \(?\), Mekyho pomocníci nedávali pozor a nezapísali, ktorý tím vyhral hru číslo \(i\) (oba tímy mohli hru potenciálne vyhrať).

Tím mohol turnaj potenciálne vyhrať, ak v reťazci \(s\) vieme nahradiť každý \(?\) buď \(0\) alebo \(1\) tak, aby daný tím turnaj vyhral.

Následuje \(q\) zmien, každá v jednom riadku vo formáte jedného celého čísla \(p\) a jedného znaku \(c\) oddelených medzerou. V rámci zmeny sa \(s_p\) zmení na znak \(c\). Po každej zmene je vašou úlohou vypísať celé číslo reprezentujúce počet potenciálnych možných víťazných tímov turnaja reprezentovaného reťazcom \(s\).

Vstup a Výstup

V prvom riadku vstupu sa nachádza celé čislo \(n\). V prvej sade platí \(1 \leq n \leq 10\), v druhej sade platí \(1 \leq n \leq 18\).

V druhom riadku sa nachádza reťazec \(s\) dĺžky \(2^n - 1\) pozostávajúci zo znakov \(0\), \(1\), \(?\), reprezentujúci pôvodný stav výsledkov turnaja.

V treťom riadku sa nachádza celé číslo \(q\) - počet zmien. V prvej sade platí \(1 \leq q \leq 1000\), v druhej sade platí \(1 \leq q \leq 100000\).

Nasledujúcich \(q\) riadkov každý obsahuje číslo \(p\) a znak \(c\) (\(1 \leq p \leq 2^n - 1\), \(c\) môže byť \(0\), \(1\) alebo \(?\)).

Pre každú zmenu v reťazci vypíšte celé číslo - počet možných víťazov turnaja reprezentovaného momentálnym reťazcom \(s\).

Príklad

Input:

Output:

Pre odovzdávanie sa musíš prihlásiť.