JOI 君 очень любит собирать изображения, и у него уже есть большая коллекция. Недавно JOI 君 заметил, что из-за слишком большого количества изображений на жёстком диске стало не хватать места. Денег на новый жёсткий диск у него нет, а удаление собственных изображений было бы для него невыносимо мучительным. Поэтому он решил уменьшить занимаемое место, хорошо сжав изображения.

Изображение состоит из $2^N$ строк и $2^N$ столбцов пикселей, образующих квадрат, то есть всего из $2^N\times 2^N$ пикселей. Каждый пиксель имеет белый или чёрный цвет.

JOI 君 решил сжимать такие изображения следующим способом.

• Если все пиксели изображения одного цвета, записывается только этот цвет. В этом случае размер сжатых данных равен $1$.
• Иначе изображение делится на 4 меньших изображения. Если изображение имеет $2^k$ строк и $2^k$ столбцов, оно разрезается посередине по вертикали и горизонтали, и получаются 4 изображения, каждое из $2^{k-1}$ строк и $2^{k-1}$ столбцов. Эти четыре меньших изображения сжимаются тем же способом. В этом случае размер сжатых данных определяется как сумма размеров сжатых данных четырёх меньших изображений плюс $1$.

JOI 君 начал сомневаться, действительно ли этот способ позволяет сжимать изображения, и решил провести эксперименты с различными изображениями. Эксперимент проводится следующим образом.

• Сначала подготавливается изображение, все пиксели которого белые.
• Для $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$ определяется размер сжатых данных, полученных сжатием изображения после операции $i$ способом JOI 君.

Чтобы выполнить в эксперименте как можно больше операций, необходимо быстро определять размер сжатых данных.

Задача

Даны целое число $N$, задающее размер изображения, число операций $Q$ и описания $Q$ операций. Напишите программу, которая для изображения после каждой операции определяет размер данных после сжатия способом JOI 君.

Входные данные

Прочитайте следующие данные из стандартного ввода.

• Первая строка содержит два целых числа $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$. Это означает, что операция $i$ меняет на противоположные цвета всех пикселей строки $X_i$ сверху, если $T_i=0$, или столбца $X_i$ слева, если $T_i=1$.

Выходные данные

Выведите в стандартный вывод $Q$ строк. В строке $i$ ($1\le i\le Q$) выведите одно целое число — размер данных, полученных сжатием изображения после операции $i$ способом JOI 君.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $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$ операции выполняются следующим образом.

Сверху показано начальное состояние