Vụ án sô cô la

Cho một thanh sô cô la hình vuông $n\times n$ ô. Các cột được đánh số từ $1$ đến $n$ theo chiều từ trái sang phải, các hàng được đánh số từ $1$ đến $n$ theo chiều từ trên xuống dưới. Ô ở cột $x$, hàng $y$ ký hiệu là $(x,y)$.

Đường chéo phụ là đường đi từ góc dưới bên trái lên góc trên bên phải, gồm các ô $(x,y)$ thỏa mãn $x+y=n+1$. Ban đầu, toàn bộ các ô nằm phía dưới đường chéo phụ đã bị ăn hết, chỉ còn lại phần tam giác gồm đường chéo phụ và các ô phía trên nó.

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

• Hướng U (lên): bắt đầu từ ô đã chọn, ăn các ô đi lên trên (giảm chỉ số hàng) theo cùng cột $x$.
• Hướng L (trái): bắt đầu từ ô đã chọn, ăn các ô đi sang trái (giảm chỉ số cột) theo cùng hàng $y$.

Việc ăn dừng lại ngay khi gặp một ô đã bị ăn trước đó hoặc gặp mép của thanh sô cô la. Nếu ô $(x,y)$ được chọn đã bị ăn từ trước thì hành động không ăn được ô nào.

Sau mỗi hành động, hãy cho biết số ô đã ăn được trong hành động đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• $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ự (U hoặc L), mô tả hành động thứ $i$. Đảm bảo $x_i+y_i=n+1$.

Dữ liệu ra

Gồm $q$ dòng, dòng thứ $i$ là số ô ăn được trong hành động 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ụ