JOI 君 sangat suka mengumpulkan banyak gambar dan telah memiliki banyak gambar. Belakangan, JOI 君 menyadari bahwa kapasitas cakram kerasnya hampir habis karena terlalu banyak mengumpulkan gambar. Ia tidak memiliki uang untuk membeli cakram keras baru, tetapi menghapus gambar miliknya akan sangat menyakitkan baginya. Oleh karena itu, ia memutuskan untuk mengompresi gambar dengan baik agar mengurangi ruang yang diperlukan.

Sebuah gambar terdiri atas $2^N$ baris dan $2^N$ kolom piksel yang tersusun membentuk persegi, sehingga terdapat $2^N\times 2^N$ piksel. Setiap piksel berwarna putih atau hitam.

JOI 君 memutuskan untuk mengompresi gambar seperti ini dengan cara berikut.

• Jika semua piksel dalam gambar memiliki warna yang sama, cukup catat warna tersebut. Dalam hal ini, ukuran data setelah dikompresi adalah $1$.
• Jika tidak, bagi gambar menjadi 4 gambar yang lebih kecil. Jika gambar memiliki $2^k$ baris dan $2^k$ kolom, potong di tengah secara vertikal dan horizontal untuk memperoleh 4 gambar, masing-masing dengan $2^{k-1}$ baris dan $2^{k-1}$ kolom. Kompres keempat gambar kecil itu dengan cara yang sama. Dalam hal ini, ukuran data setelah dikompresi didefinisikan sebagai jumlah ukuran data hasil kompresi keempat gambar kecil tersebut, ditambah $1$.

JOI 君 mulai khawatir apakah cara ini benar-benar dapat mengompresi gambar, sehingga ia memutuskan untuk melakukan percobaan dengan berbagai gambar. Cara percobaannya adalah sebagai berikut.

• Pertama, siapkan sebuah gambar yang semua pikselnya berwarna putih.
• Untuk $i=1,\ldots,Q$, lakukan operasi berikut: jika $T_i=0$, balik warna hitam dan putih pada semua $2^N$ piksel di baris ke-$X_i$ dari atas; jika $T_i=1$, balik warna hitam dan putih pada semua $2^N$ piksel di kolom ke-$X_i$ dari kiri. Dengan kata lain, tuliskan $(a,b)$ untuk piksel pada baris ke-$a$ dari atas dan kolom ke-$b$ dari kiri. Untuk setiap $i$, jika $T_i=0$, ubah semua piksel $(X_i,b)$ yang memenuhi $1\le b\le 2^N$; jika $T_i=1$, ubah semua piksel $(a,X_i)$ yang memenuhi $1\le a\le 2^N$. Piksel putih diubah menjadi hitam, dan piksel hitam diubah menjadi putih.
• Untuk setiap $i$, tentukan ukuran data setelah gambar yang dihasilkan sesudah operasi ke-$i$ dikompresi dengan cara JOI 君.

Agar dapat melakukan sebanyak mungkin operasi dalam percobaan, ukuran data hasil kompresi harus ditentukan dengan cepat.

Tugas

Diberikan bilangan bulat $N$ yang menyatakan ukuran gambar, banyaknya operasi $Q$, serta instruksi untuk $Q$ operasi tersebut. Buatlah program yang menentukan ukuran data setelah gambar yang dihasilkan sesudah setiap operasi dikompresi dengan cara JOI 君.

Masukan

Baca data berikut dari masukan standar.

• Baris pertama berisi dua bilangan bulat $N,Q$ yang dipisahkan oleh spasi. Ini menyatakan bahwa gambar berukuran $2^N$ baris dan $2^N$ kolom, serta terdapat $Q$ operasi.
• $Q$ baris berikutnya berisi instruksi operasi. Baris ke-$i$ dari baris-baris ini ($1\le i\le Q$) berisi dua bilangan bulat $T_i,X_i$ yang dipisahkan oleh spasi, dengan $0\le T_i\le 1$ dan $1\le X_i\le 2^N$. Ini menyatakan bahwa operasi ke-$i$ membalik warna hitam dan putih semua piksel pada baris ke-$X_i$ dari atas jika $T_i=0$, atau pada kolom ke-$X_i$ dari kiri jika $T_i=1$.

Keluaran

Tuliskan $Q$ baris ke keluaran standar. Pada baris ke-$i$ ($1\le i\le Q$), tuliskan sebuah bilangan bulat yang menyatakan ukuran data hasil kompresi gambar setelah operasi ke-$i$ menggunakan cara JOI 君.

Batasan

Semua data masukan memenuhi syarat-syarat berikut.

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

Subsoal

Subsoal 1 [10 poin]

Memenuhi syarat-syarat berikut.

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

Subsoal 2 [20 poin]

Memenuhi syarat-syarat berikut.

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

Subsoal 3 [70 poin]

• Tidak ada batasan tambahan.

Contoh

Masukan 1

2 3
0 1
1 2
0 3

Keluaran 1

13
17
21

Penjelasan

Dalam contoh ini, $Q=3$ operasi dilakukan seperti berikut.

Keadaan awal ditunjukkan paling atas