Sau khi mua một nùi truyện segg về, Loli cần phải cất giữ chúng ở trong một kệ sách. Kệ sách nhà Loli có ~n~ vị trí để đựng sách, các vị trí được đánh số lần lượt từ ~1~ tới ~n~. Ban đầu sẽ không có sách trên kệ. Mỗi ngày, Loli sẽ thực hiện một số thay đổi trên kệ sách. Có ~4~ hành động Loli có thể làm:

• ~1\ x~: Đặt một cuốn sách vào vị trí thứ ~x~. Nếu đã có sách ở vị trí ~x~ từ trước, giữ nguyên.
• ~2\ x~: Lấy cuốn sách (nếu có) ở vị trí thứ ~x~ ra.
• ~3~: Đảo ngược trạng thái trên kệ. Những vị trí có sách sẽ được lấy ra, và những vị trí không có sách sẽ được thêm sách vào.
• ~4\ x~: Đưa kệ sách trở về quá khứ, trạng thái kệ sách y hệt như ngày thứ ~x~. Nếu ~x=0~, thì trạng thái sẽ là ban đầu – tức là khi chưa có sách.

Sau mỗi ngày Loli muốn biết có bao nhiêu sách trên kệ. Bạn hãy code giúp Loli nhé!

Input:

Lấy từ tệp SHELF.INP gồm:

• Dòng đầu tiên chứa số nguyên ~n\ (1\le n\le4000)~ – số vị trí trong kệ sách.
• Dòng tiếp theo chứa số nguyên ~q\ (1\le q\le5\times10^5)~ – số ngày cần tính.
• ~q~ dòng cuối cùng chứa các hành động trong ~q~ ngày theo quy ước phía trên.

Output:

Ghi ra tệp SHELF.OUT:

• Gồm ~q~ dòng, mỗi dòng chứa một số thể hiện số sách trên kệ vào ngày đó.

Sample Input 1

4
4
1 1
3
2 4
4 0

Sample Output 1

1
3
2
0

Ràng buộc

• 30% số test có ~q\le10^3~.
• 30% số test có ~n\le150~.
• 40% số test không có ràng buộc gì thêm.