JOI суреттер жинауды жақсы көреді және оның суреттері өте көп. Жақында JOI тым көп сурет жинағандықтан, қатты дискісінде орын таусылып бара жатқанын байқады. Оның жаңа қатты диск сатып алуға шамасы жоқ, ал суреттерінің кез келгенін өшіру оған өте ауыр тиеді, сондықтан ол орын үнемдеу үшін суреттерін сығуды (компрессиялауды) ұйғарды.

Сурет $2^N$ жол мен $2^N$ бағаннан тұратын шаршы торда орналасқан барлығы $2^N \times 2^N$ пиксельмен беріледі. Әрбір пиксель ақ немесе қара түсті болады.

JOI мұндай суретті келесі әдіспен сығуды шешті:

• Егер суреттегі барлық пиксельдердің түсі бірдей болса, тек сол түсті жазып қояды. Бұл жағдайда сығылған деректердің өлшемі $1$-ге тең.
• Әйтпесе, суретті төрт кішірек суретке бөледі. Егер сурет $2^k$ жол мен $2^k$ бағаннан тұрса, суретті тігінен де, көлденеңінен де дәл ортасынан бөліп, $2^{k-1}$ жол мен $2^{k-1}$ бағаннан тұратын төрт сурет алады. Осы төрт кішірек суретті дәл сол әдіспен сығады. Бұл жағдайда сығылған деректердің өлшемі төрт кішірек суреттің сығылған деректерінің өлшемдерінің қосындысына $1$-ді қосқанға тең болады.

JOI бұл әдіс суреттерді шынымен сыға ала ма деп уайымдап, әртүрлі суреттермен тәжірибе жасап көруді ұйғарды. Тәжірибе әдісі келесідей:

• Алдымен, барлық пиксельдері ақ түсті сурет дайындалады.
• $i = 1, \dots, Q$ үшін келесі амал орындалады: "Егер $T_i = 0$ болса, жоғарыдан санағанда $X_i$-ші жолдағы барлық $2^N$ пиксельдің түсін кері ауыстырыңыз (ақты қараға, қараны аққа). Егер $T_i = 1$ болса, сол жақтан санағанда $X_i$-ші бағандағы барлық $2^N$ пиксельдің түсін кері ауыстырыңыз." Яғни, жоғарыдан $a$-шы жолда және сол жақтан $b$-шы бағанда орналасқан пиксельді $(a, b)$ деп белгілесек, әрбір $i$ үшін, егер $T_i = 0$ болса, барлық $1 \le b \le 2^N$ үшін $(X_i, b)$ пиксельдеріне амал орындалады, ал егер $T_i = 1$ болса, барлық $1 \le a \le 2^N$ үшін $(a, X_i)$ пиксельдеріне амал орындалады.
• Әрбір $i$ үшін, $i$-ші амалдан кейінгі суретті JOI әдісімен сыққан кездегі сығылған деректердің өлшемін анықтаңыз.

Тәжірибеде мүмкіндігінше көп амал орындау үшін сығылған деректердің өлшемін жоғары жылдамдықпен анықтау қажет.

Тапсырма

Суреттің өлшемін білдіретін бүтін сан $N$, амалдар саны $Q$ және $Q$ амалға арналған нұсқаулар берілген. Әрбір амалдан кейін JOI әдісімен сығылған деректердің өлшемін есептейтін программа жазыңыз.

Кіріс деректер

Стандартты кірістен келесі мәліметтерді оқыңыз:

• Бірінші жолда бос орынмен бөлінген екі бүтін сан $N$ және $Q$ берілген, олар суреттің өлшемі $2^N \times 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$-ші амал $T_i = 0$ болғанда жоғарыдан $X_i$-ші жолдағы барлық пиксельдердің түсін, ал $T_i = 1$ болғанда сол жақтан $X_i$-ші бағандағы барлық пиксельдердің түсін кері ауыстыратынын білдіреді.

Шығыс деректер

Стандартты шығысқа $Q$ жол шығарыңыз. $i$-ші жолда ($1 \le i \le Q$) $i$-ші амалдан кейінгі сығылған деректердің өлшемін білдіретін бір бүтін сан болуы тиіс.

Шектеулер

Барлық кіріс деректері келесі шарттарды қанағаттандырады:

• $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 2048$.

Ішкі есеп 3 [70 ұпай]

• Қосымша шектеулер жоқ.

Мысалдар

Кіріс деректер 1

2 3
0 1
1 2
0 3

Шығыс деректер 1

13
17
21

Ескертпе

Бұл мысалда $Q = 3$ амал келесідей орындалады:

Бастапқы күй: □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□