Nejaukais trijstūris

Acīgais arheologs Šņitrāms savos pasaules apceļojumos ir uzgājis senas civilizācijas drupas. Drupās viņš ir atradis lielu kambari ar milzīgu trijstūrveida struktūru tā vidū. Šī struktūra ir sadalīta mazākos trijstūra formas lauciņos - katra lielā trijstūra mala sadalīta $N$ vienādās daļās un novilkti abām pārējām malām paralēli nogriežņi. Lielajā trijstūrī katrai no trim pusēm (1. attēlā attiecīgi $A$, $B$ un $C$) mazie trijstūrīši ir sadalīti pa rindām, kas indeksētas ar skaitļiem no $1$ līdz $N$, un $i$-tajā rindā ir $2i - 1$ mazais trijstūrītis (skat. 1. attēlu).

Šņitrāms ir izpētījis kambari un pie sienas atradis senu artefaktu, ar kuru var lielajā trijstūrī pa izvēlētu malu ($A$, $B$ vai $C$) šaut gaismas staru kādā no $N$ rindām. Šaujot staru rindā $i$, stars izies cauri visiem šajā rindā esošajiem $2i - 1$ mazajiem trijstūrīšiem.

Izrādās, ka katrā no mazajiem trijstūrīšiem dzīvo sena radība - drupu čukstētājs! Katrs drupu čukstētājs var būt vai nu paslēpies vai redzams. Visiem mazajiem trijstūriem, kuriem trāpa artefakta stars, notiek sekojošais:

• ja trijstūrī dzīvojošais drupu čukstētājs ir paslēpies, tad tas, ziņkāres mākts, atstāj savu slēptuvi un kļūst redzams;
• ja trijstūrī dzīvojošais drupu čukstētājs ir redzams, tad spožā gaisma to apžilbina un tas paslēpjas.

Lai atvērtu lielās durvis kambara galā, Šņitrāmam ir jāizpilda uz sienas uzrakstītas instrukcijas, kas nosaka, ka artefakta kārtējais stars jāšauj noteiktas trijstūra malas rindā ar indeksu $i$. Pēc katras instrukcijas veikšanas Šņitrāmam ir jānosaka, cik drupu čukstētāji šobrīd ir redzami. Viens instrukciju izpildes piemērs un redzamo drupu čukstētāju skaits pēc katras instrukcijas izpildes ir parādīts 2. attēlā.

Drupu čukstētājiem šķiet nejauki, ka viņus tik bieži apžilbina, tāpēc lielais trijstūris ir iesaukts par "Nejauko trijstūri".

Uzrakstiet datorprogrammu, kas dotām $N$ un $Q$ vērtībām un $Q$ instrukcijām nosaka redzamo drupu čukstētāju skaitu pēc katras instrukcijas!

Pirmajā rindā doti divi naturāli skaitļi - rindu skaits katrā malā $N (1 \leq N \leq 10^5)$ un instrukciju skaits $Q (1 \leq Q \leq 10^5)$. Tad seko $Q$ rindas, kas katra ir vienas instrukcijas apraksts - trijstūra malas apzīmējošs burts $M (M \in \{A, B, C\})$ un rindas numurs $i (1 \leq i \leq N)$.

Starp katriem diviem blakus skaitļiem, kā arī starp burtu un skaitli ievaddatos ir tukšumzīme.

Izvaddatiem jāsastāv no $Q$ rindām, kur $i$-tajai rindai jāsatur redzamo drupu čukstētāju skaits pēc izpildītām pirmajām $i$ instrukcijām.