Sau nhiều năm chiến đấu, bảo về bộ lạc, săn lùng kẻ ác, Piccôlô giờ đảm nhiệm vai trò "trông trẻ". Hắn nhận đào tạo Son Gohan, và có rất nhiều thời gian trong tay để làm những điều hắn muốn. Một trong số đó là chơi TETRIS.

Trò chơi TETRIS có bảy loại khối hình, hay còn gọi là Tetromino: I (thẳng đứng), J, L, O (vuông), S, T, Z; mỗi khối hình bao gồm 4 viên gạch. Ta cần phải thả các khối hình, tương ứng với bảy loại này vào một bảng vuông có độ rộng là ~W~.

Khi bắt đầu một vòng chơi mới, tetromino đầu tiên sẽ rơi từ trên cùng của màn hình xuống phía dưới. Người chơi có thể di chuyển, xoay và thả nó để tạo ra các hàng hoặc cột hoàn chỉnh để ghi điểm và giải phóng không gian. Một tetromino mới sẽ được trò chơi sinh ra ~1~ trong ~7~ loại trên, nó thể được xoay 0 độ, 90 độ, 180 độ, hoặc 270 độ. Nó sẽ dừng lại khi một trong bốn ô của tetromino gặp phải vật cản trên cùng cột với nó. Khi đó, tetromino giữ vị trí cố định, và tetromino mới bắt đầu rơi xuống. Nếu sau khi một tetromino được giữ cố định, mà tạo ra một số hàng được lấp đầy bởi các viên tetromino, hàng đó sẽ biến mất, và người chơi được cộng điểm.

Piccôlô chơi Tetris, và bạn có danh sách nước đi của hắn ta. Mỗi nước đi sẽ được thể hiện qua ba dữ kiện:

• ~s_i~ là một trong bảy ký tự: 'I', 'J', 'L', 'O', 'S', 'T', 'Z', thể hiện hình dạng của Tetromino rơi xuống ở nước đi này.

• ~r_i~ thể hiện góc quay của viên gạch, theo chiều kim đồng hồ. Giá trị này có thể là một trong bốn số: ~0~, ~90~, ~180~, ~270~.

• ~c_i~ thể hiện chỉ số cột mà Tetromino này sẽ rơi xuống. Cụ thể, chỉ số này là cột mà ô ngoài cùng bên trái của Tetromino sẽ rơi xuống.

Ngoài ra, hắn còn một nước đi đặc biệt: khôi phục trò chơi về trước nước đi thứ ~i~ nào đó. Hắn có thể làm thế tùy thích, chẳng hạn nếu như cảm thấy mình có thể có nước đi tốt hơn có thể đi lại từ nước đi này. Đồng thời, khác với chế độ TETRIS cơ bản, hắn có thể để cho các tetromino của mình lên độ cao tùy ý mà không bị thua (chiều cao của bảng là vô hạn).

Nhiệm vụ của bạn, sau mỗi nước đi của Piccôlô, hãy in ra độ cao của hàng lớn nhất, mà xuất hiện một phần của một Tetromino.

Input

Dòng đầu chứa hai số nguyên ~W~ (~1 \leq W \leq 10000~) và ~N~ (~1 \leq N \leq 50000~) lần lượt là chiều rộng của bảng chơi và số lượt chơi.

~N~ dòng tiếp theo, mỗi dòng mô tả 1 lượt chơi.

• Piccôlô có thể thực hiện nước đi thứ ~i~ là thả viên gạch mới. Khi đó, nước đi này sẽ có dạng: "~s_i\ r_i \ c_i~" (~r_i \in \{0, 90, 180, 270\}~, ~0 \leq c_i \lt W~), lần lượt thể hiện hình dạng, chiều quay, và chỉ số cột của viên gạch này.

• Piccôlô có thể thực hiện nước đi thứ ~i~ là khôi phục lại về nước đi ~m_i~ nào đó. Khi đó, nước đi này sẽ có dạng "~.\ m_i~", ~m_i~ thể hiện chỉ số của nước đi mà Piccôlô có thể khôi phục về.

Output

• Tương ứng với mỗi lượt chơi, in ra trên một dòng độ cao của viên gạch cao nhất đang tồn tại trong bảng.

Sample Input 1

5 11
I 90 0
J 270 2
L 270 2
T 90 0
Z 90 0
O 180 2
S 90 3
. 5
J 90 2
. 0
T 180 1

Sample Output 1

1
1
3
2
4
3
3
4
3
0
2

Notes

Với test ví dụ, trạng thái của bảng sau các lượt chơi như sau:

1)
****.

2)
..***

3)
....*
..***
..***

4)
.*..*
.****

5)
.*...
**...
**..*
.****

6)
.*...
****.
.****

7)
...*.
.*.**
.****

8)
.*...
**...
**..*
.****

9)
.**..
**..*
.****

10)
.....

11)
..*..
.***.