Bài toán thao tác ma trận đặc biệt: cho ma trận ~A~ kích thước ~N\times N~ với ~A[i,j]=i+j~. Mỗi truy vấn xóa hàng/cột sẽ tính tổng theo hàng/ cột đang còn hiệu lực rồi gán các phần tử tương ứng về ~0~. Yêu cầu xử lý ~Q~ truy vấn tuần tự, chú ý các ảnh hưởng chéo giữa những hàng/ cột đã bị xóa trước đó.

Yêu cầu

Cho ma trận ~A~ kích thước ~N\times N~ với ~A[i,j]=i+j~ ~(1\le i,j\le N)~.
Thực hiện ~Q~ truy vấn, mỗi truy vấn có một trong hai dạng:

• ~R~ ~r~: Tính tổng các phần tử hiện còn trên hàng ~r~, sau đó gán toàn bộ phần tử hàng ~r~ bằng ~0~.
• ~C~ ~c~: Tính tổng các phần tử hiện còn trên cột ~c~, sau đó gán toàn bộ phần tử cột ~c~ bằng ~0~.

In ra giá trị tổng cho từng truy vấn theo đúng thứ tự.

Dữ liệu

• Dòng đầu: hai số nguyên dương ~N~, ~Q~ ~(1\le N\le 10^6,\ 1\le Q\le 10^5)~.
• ~Q~ dòng tiếp theo: mỗi dòng là một truy vấn:
  • ~R~ ~r~ với ~1\le r\le N~, hoặc
  • ~C~ ~c~ với ~1\le c\le N~.

Kết quả

• Gồm ~Q~ dòng, dòng thứ ~i~ là kết quả (tổng) của truy vấn thứ ~i~.

Ví dụ

Ví dụ 1

Input

3 5
R 1
C 3
R 2
R 1
C 2

Output

9
11
7
0
5