JOI uwielbia zbierać obrazki i ma ich bardzo wiele. Niedawno zauważył, że przez zgromadzenie zbyt wielu obrazków zaczyna brakować mu miejsca na dysku. Nie ma pieniędzy na zakup nowego dysku, a usunięcie posiadanych obrazków byłoby dla niego niezwykle bolesne. Postanowił więc zmniejszyć zajmowane miejsce, odpowiednio kompresując obrazy.

Obraz jest reprezentowany przez $2^N\times2^N$ pikseli ułożonych w kwadrat o $2^N$ wierszach i $2^N$ kolumnach. Każdy piksel jest biały albo czarny.

JOI postanowił kompresować takie obrazy następującą metodą.

• Jeśli wszystkie piksele obrazu mają ten sam kolor, zapisujemy tylko ten kolor. Rozmiar danych po kompresji wynosi wtedy $1$.
• W przeciwnym razie dzielimy obraz na 4 mniejsze obrazy. Jeśli obraz ma $2^k$ wierszy i $2^k$ kolumn, dzielimy go w połowie w obu kierunkach, otrzymując cztery obrazy o $2^{k-1}$ wierszach i $2^{k-1}$ kolumnach. Każdy z nich kompresujemy tą samą metodą. Rozmiar danych po kompresji jest wówczas sumą rozmiarów skompresowanych danych czterech mniejszych obrazów, powiększoną o $1$.

JOI zaczął się obawiać, czy ta metoda rzeczywiście kompresuje obrazy, i postanowił przeprowadzić eksperymenty na różnych obrazach. Eksperyment wygląda następująco.

• Najpierw przygotowujemy obraz, w którym wszystkie piksele są białe.
• Dla $i=1,\ldots,Q$ wykonujemy operację: jeśli $T_i=0$, odwracamy kolor każdego z $2^N$ pikseli w wierszu $X_i$ od góry, a jeśli $T_i=1$, odwracamy kolor każdego z $2^N$ pikseli w kolumnie $X_i$ od lewej. Dokładniej, oznaczmy element w wierszu $a$ od góry i kolumnie $b$ od lewej przez $(a,b)$. Dla każdego $i$, jeśli $T_i=0$, zmieniamy kolor pikseli $(X_i,b)$ dla $1\le b\le2^N$, a jeśli $T_i=1$, zmieniamy kolor pikseli $(a,X_i)$ dla $1\le a\le2^N$: biały na czarny, a czarny na biały.
• Dla każdego $i$ sprawdzamy rozmiar danych po skompresowaniu metodą JOI obrazu otrzymanego po operacji numer $i$.

Aby wykonać w eksperymencie jak najwięcej operacji, trzeba szybko wyznaczać rozmiar danych po kompresji.

Zadanie

Dane są liczba całkowita $N$ opisująca rozmiar obrazu, liczba operacji $Q$ oraz instrukcje $Q$ operacji. Napisz program obliczający po każdej operacji rozmiar danych po skompresowaniu otrzymanego obrazu metodą JOI.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera dwie liczby całkowite $N,Q$, oddzielone spacją. Oznaczają one, że obraz ma $2^N$ wierszy i $2^N$ kolumn, a liczba operacji wynosi $Q$.
• Kolejnych $Q$ wierszy zawiera instrukcje operacji. Wiersz numer $i$ ($1\le i\le Q$) zawiera dwie liczby całkowite $T_i,X_i$ ($0\le T_i\le1$ oraz $1\le X_i\le2^N$), oddzielone spacją. Jeśli $T_i=0$, operacja numer $i$ odwraca kolory wszystkich pikseli w wierszu $X_i$ od góry; jeśli $T_i=1$, odwraca kolory wszystkich pikseli w kolumnie $X_i$ od lewej.

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. W wierszu numer $i$ ($1\le i\le Q$) wypisz jedną liczbę całkowitą oznaczającą rozmiar danych po skompresowaniu metodą JOI obrazu otrzymanego po operacji numer $i$.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $1\le N\le20$.
• $1\le Q\le2\,000\,000$.

Podzadania

Podzadanie 1 [10 punktów]

Spełnione są następujące warunki.

• $N\le6$.
• $Q\le128$.

Podzadanie 2 [20 punktów]

Spełnione są następujące warunki.

• $N\le10$.
• $Q\le2\,048$.

Podzadanie 3 [70 punktów]

• Nie ma dodatkowych ograniczeń.

Przykład

Wejście 1

2 3
0 1
1 2
0 3

Wyjście 1

13
17
21

Uwagi

W tym przykładzie $Q=3$ operacje przebiegają następująco.

Stan początkowy