Thanh sô-cô-la

Một thanh sô-cô-la được biểu diễn bằng bảng $n\times n$ ô. Các cột đánh số từ $1$ đến $n$ từ trái sang phải, các hàng đánh số từ $1$ đến $n$ từ trên xuống dưới. Ô ở cột $x$, hàng $y$ được ký hiệu là $(x,y)$.

Đường chéo phụ là đường chéo đi từ góc dưới bên trái tới góc trên bên phải, tức là tập các ô $(x,y)$ với $x+y=n+1$.

Đầu tiên, toàn bộ các ô nằm phía dưới đường chéo phụ (các ô có $x+y>n+1$) đã bị ăn hết. Phần còn lại là một tam giác gồm các ô có $x+y\le n+1$.

Sau đó, có $q$ thao tác được thực hiện lần lượt. Mỗi thao tác chọn một ô $(x,y)$ nằm trên đường chéo phụ và một hướng:

• Hướng U (lên trên): đi từ ô $(x,y)$ theo chiều giảm dần của hàng.
• Hướng L (sang trái): đi từ ô $(x,y)$ theo chiều giảm dần của cột.

Bắt đầu từ chính ô $(x,y)$, ta ăn từng ô một theo hướng đã chọn, và dừng lại ngay khi gặp một ô đã bị ăn trước đó hoặc khi đi ra ngoài thanh sô-cô-la. Lưu ý rằng nếu bản thân ô $(x,y)$ đã bị ăn từ trước thì thao tác đó không ăn được ô nào.

Với mỗi thao tác, hãy cho biết số ô bị ăn trong thao tác đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$: kích thước thanh sô-cô-la và số thao tác.
• $q$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$, $y_i$ và một ký tự là U hoặc L, mô tả thao tác thứ $i$.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là số ô bị ăn trong thao tác thứ $i$.

Ràng buộc

• $1\le n\le {10}^9$
• $1\le q\le 2·{10}^5$
• $1\le x_i,y_i\le n$ và $x_i+y_i=n+1$

Ví dụ