JOI rất thích sưu tầm ảnh và có rất nhiều ảnh. Gần đây, JOI nhận ra rằng vì thu thập quá nhiều ảnh nên ổ cứng sắp hết chỗ. Cậu không có tiền mua ổ cứng mới, nhưng việc xóa những bức ảnh mình có lại vô cùng đau khổ, nên cậu quyết định giảm dung lượng bằng cách nén ảnh một cách khéo léo.

Một ảnh gồm tổng cộng $2^N\times2^N$ điểm ảnh, xếp thành hình vuông có $2^N$ hàng và $2^N$ cột. Mỗi điểm ảnh có màu trắng hoặc đen.

JOI quyết định nén ảnh như sau:

• Nếu mọi điểm ảnh trong ảnh đều cùng màu, chỉ ghi lại màu đó. Khi ấy, kích thước dữ liệu sau nén là $1$.
• Nếu không, chia ảnh thành bốn ảnh nhỏ hơn. Với ảnh có $2^k$ hàng và $2^k$ cột, chia đôi ở giữa theo cả chiều dọc và chiều ngang để được bốn ảnh có $2^{k-1}$ hàng và $2^{k-1}$ cột. Nén bốn ảnh nhỏ này theo cùng phương pháp. Kích thước dữ liệu sau nén bằng tổng kích thước sau nén của bốn ảnh nhỏ, cộng thêm $1$.

JOI không chắc phương pháp này có thực sự nén được ảnh hay không, nên quyết định thử nghiệm với nhiều ảnh khác nhau. Cách thử nghiệm như sau:

• Ban đầu, chuẩn bị một ảnh có mọi điểm ảnh đều màu trắng.
• Với $i=1,\ldots,Q$, thực hiện thao tác: nếu $T_i=0$, đảo màu trắng và đen của $2^N$ điểm ảnh trên hàng thứ $X_i$ tính từ trên xuống; nếu $T_i=1$, đảo màu của $2^N$ điểm ảnh trên cột thứ $X_i$ tính từ trái sang. Cụ thể, gọi điểm ảnh ở hàng thứ $a$ từ trên xuống và cột thứ $b$ từ trái sang là $(a,b)$. Trong thao tác thứ $i$, nếu $T_i=0$, đổi trắng thành đen và đen thành trắng tại mọi điểm ảnh $(X_i,b)$ với $1 \le b \le 2^N$; nếu $T_i=1$, làm tương tự tại mọi điểm ảnh $(a,X_i)$ với $1 \le a \le 2^N$.
• Với mỗi $i$, xác định kích thước dữ liệu sau khi nén ảnh thu được sau thao tác thứ $i$ bằng phương pháp của JOI.

Để thực hiện được càng nhiều thao tác càng tốt trong thí nghiệm, cần tính kích thước dữ liệu sau nén thật nhanh.

Nhiệm vụ

Cho số nguyên $N$ biểu thị kích thước ảnh, số thao tác $Q$ và chỉ dẫn cho $Q$ thao tác. Hãy viết chương trình tính kích thước dữ liệu sau khi nén ảnh bằng phương pháp của JOI sau mỗi thao tác.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu chứa hai số nguyên $N,Q$ cách nhau bởi dấu cách, cho biết ảnh có $2^N$ hàng và $2^N$ cột, và có $Q$ thao tác.
• $Q$ dòng tiếp theo mô tả các thao tác. Dòng thứ $i$ ($1 \le i \le Q$) chứa hai số nguyên $T_i,X_i$ cách nhau bởi dấu cách, với $0 \le T_i \le 1$ và $1 \le X_i \le 2^N$. Nếu $T_i=0$, thao tác thứ $i$ đảo màu mọi điểm ảnh trên hàng thứ $X_i$ từ trên xuống; nếu $T_i=1$, đảo màu mọi điểm ảnh trên cột thứ $X_i$ từ trái sang.

Dữ liệu ra

Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $i$ ($1 \le i \le Q$) chứa một số nguyên biểu thị kích thước dữ liệu sau khi nén ảnh thu được sau thao tác thứ $i$ bằng phương pháp của JOI.

Giới hạn

Mọi dữ liệu vào đều thỏa mãn các điều kiện sau.

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

Nhiệm vụ con

Nhiệm vụ con 1 [10 điểm]

Thỏa mãn các điều kiện sau.

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

Nhiệm vụ con 2 [20 điểm]

Thỏa mãn các điều kiện sau.

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

Nhiệm vụ con 3 [70 điểm]

• Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

2 3
0 1
1 2
0 3

Dữ liệu ra 1

13
17
21

Ghi chú

Trong ví dụ này, $Q=3$ thao tác được thực hiện như sau.

Trạng thái ban đầu.