JOI rất thích sưu tầm ảnh và đã lưu được rất nhiều ảnh. Gần đây, ổ cứng của cậu sắp hết chỗ. Vì không có tiền mua ổ cứng mới và không muốn xóa ảnh, cậu quyết định nén chúng.

Mỗi ảnh là một bảng vuông có \(2^N\) hàng và \(2^N\) cột, gồm tổng cộng \(2^N\times2^N\) điểm ảnh. Mỗi điểm ảnh có màu trắng hoặc đen. JOI nén ảnh theo quy tắc sau:

• Nếu tất cả điểm ảnh có cùng màu, chỉ ghi lại màu đó. Kích thước dữ liệu sau khi nén là \(1\).
• Nếu không, chia ảnh thành bốn ảnh vuông bằng nhau bằng cách cắt ở chính giữa theo cả chiều ngang lẫn chiều dọc. Với ảnh có kích thước \(2^k\times2^k\), mỗi ảnh nhỏ có kích thước \(2^{k-1}\times2^{k-1}\). Nén từng ảnh nhỏ theo cùng quy tắc. Kích thước dữ liệu sau khi nén bằng tổng kích thước nén của bốn ảnh nhỏ cộng thêm \(1\).

Để thử phương pháp này, JOI bắt đầu với một ảnh hoàn toàn trắng rồi thực hiện lần lượt \(Q\) thao tác. Thao tác thứ \(i\) được mô tả bởi hai số \(T_i,X_i\):

• Nếu \(T_i=0\), đảo màu tất cả \(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 tất cả \(2^N\) điểm ảnh trên cột thứ \(X_i\) tính từ trái sang.

Đảo màu nghĩa là đổi trắng thành đen và đen thành trắng. Cụ thể, gọi \((a,b)\) là điểm ảnh ở hàng \(a\), cột \(b\): khi \(T_i=0\), đảo màu các điểm \((X_i,b)\) với \(1\le b\le2^N\); khi \(T_i=1\), đảo màu các điểm \((a,X_i)\) với \(1\le a\le2^N\). Các thao tác được thực hiện liên tiếp trên ảnh hiện tại.

Sau mỗi thao tác, JOI muốn biết kích thước của ảnh khi nén bằng phương pháp trên. Cậu cần tính nhanh để thực hiện được nhiều thao tác thử nghiệm.

Yêu cầu

Cho \(N\), \(Q\) và mô tả các thao tác, hãy tính kích thước dữ liệu sau khi nén ảnh ngay sau mỗi thao tác.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(T_i,X_i\), mô tả thao tác thứ \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(i\) chứa một số nguyên là kích thước dữ liệu sau khi nén ảnh ngay sau thao tác thứ \(i\).

Ràng buộc

• Giới hạn thời gian: 5 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N\le20\).
• \(1\le Q\le2000000\).
• \(T_i\in\{0,1\}\) và \(1\le X_i\le2^N\).

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(N\le6\), \(Q\le128\).
• Nhóm 2 (20 điểm): \(N\le10\), \(Q\le2048\).
• Nhóm 3 (70 điểm): Không có ràng buộc bổ sung.

2 3
0 1
1 2
0 3

13
17
21

Ảnh có kích thước \(4\times4\). Quy ước 0 là trắng và 1 là đen, trạng thái các hàng qua ba thao tác như sau:

Kích thước nén sau các thao tác lần lượt là \(13\), \(17\) và \(21\).