JOI-kun дуже любить збирати зображення й уже має їх чимало. Нещодавно він помітив, що через надто велику колекцію на жорсткому диску майже не залишилося місця. Грошей на новий диск у нього немає, а видаляти зображення для нього нестерпно болісно. Тому він вирішив зменшити зайняте місце, вдало стиснувши зображення.

Зображення складається з $2^N$ рядків і $2^N$ стовпців пікселів, розташованих у квадраті, тобто загалом містить $2^N\times2^N$ пікселів. Кожен піксель білий або чорний.

JOI-kun вирішив стискати такі зображення наведеним нижче способом.

• Якщо всі пікселі зображення одного кольору, записується лише цей колір. Розмір стиснених даних дорівнює $1$.
• Інакше зображення розбивається на чотири менші. Якщо воно має $2^k$ рядків і $2^k$ стовпців, його ділять посередині по вертикалі й горизонталі, отримуючи чотири зображення розміром $2^{k-1}\times2^{k-1}$. Кожне з них стискається тим самим способом. Розмір стиснених даних дорівнює сумі розмірів стиснених даних чотирьох менших зображень плюс $1$.

JOI-kun засумнівався, чи справді цей спосіб дає змогу стискати зображення, і вирішив провести експерименти з різними зображеннями. Експеримент відбувається так.

• Спочатку готується зображення, усі пікселі якого білі.
• Для $i=1,\ldots,Q$ виконується операція: якщо $T_i=0$, інвертуються кольори всіх $2^N$ пікселів рядка $X_i$ згори; якщо $T_i=1$, інвертуються кольори всіх $2^N$ пікселів стовпця $X_i$ зліва. Точніше, позначимо через $(a,b)$ піксель у рядку $a$ згори та стовпці $b$ зліва. Для кожного $i$, якщо $T_i=0$, у всіх пікселів $(X_i,b)$ з $1 \le b \le 2^N$ білий колір замінюється чорним, а чорний — білим. Якщо $T_i=1$, така сама зміна виконується для всіх пікселів $(a,X_i)$ з $1 \le a \le 2^N$.
• Для кожного $i$ визначається розмір даних після стискання зображення способом JOI-kun після виконання операції $i$.

Щоб виконати якомога більше операцій під час експерименту, потрібно швидко визначати розмір стиснених даних.

Завдання

За цілим числом $N$, яке задає розмір зображення, кількістю операцій $Q$ та описом цих $Q$ операцій напишіть програму, яка знаходить розмір даних після стискання зображення способом JOI-kun після кожної операції.

Вхідні дані

Прочитайте наведені нижче дані зі стандартного вводу.

• Перший рядок містить два цілі числа $N,Q$, розділені пробілом. Зображення має $2^N$ рядків і $2^N$ стовпців, а кількість операцій дорівнює $Q$.
• Наступні $Q$ рядків описують операції. Рядок $i$ ($1 \le i \le Q$) містить два цілі числа $T_i,X_i$ ($0 \le T_i \le 1$ та $1 \le X_i \le 2^N$), розділені пробілом. Якщо $T_i=0$, операція $i$ інвертує кольори всіх пікселів рядка $X_i$ згори; якщо $T_i=1$ — стовпця $X_i$ зліва.

Вихідні дані

Виведіть $Q$ рядків у стандартний вивід. У рядку $i$ ($1 \le i \le Q$) виведіть одне ціле число — розмір стиснених даних зображення після операції $i$, якщо стискати його способом JOI-kun.

Обмеження

Усі вхідні дані задовольняють такі умови.

• $1 \le N \le 20$.
• $1 \le Q \le 2\,000\,000$.

Підзадачі

Підзадача 1 [10 балів]

Виконуються такі умови.

• $N \le 6$.
• $Q \le 128$.

Підзадача 2 [20 балів]

Виконуються такі умови.

• $N \le 10$.
• $Q \le 2\,048$.

Підзадача 3 [70 балів]

• Додаткових обмежень немає.

Приклади

Вхідні дані 1

2 3
0 1
1 2
0 3

Вихідні дані 1

13
17
21

Пояснення

У цьому прикладі $Q=3$ операції виконуються так.

Початковий стан