Settlement Office

Interview

Time limit1sMemory limit256 MB

Summary

Report each row or column sum in a grid holding x plus y, zeroing that row or column after each query.

Level: Easy3 of 10
Topics: Hash map, Math
Solved: No attempts yet

Problem

Garison and Andreson work at a settlement office and want to predict the future. They are given a large $n \times n$ square grid. At the start the element at $(x, y)$ holds $x + y$ ( $1 \le x, y \le n$ ).

Two kinds of queries arrive.

R r: print the sum of every value in row $r$ , then set all of row $r$ to 0.
C c: print the sum of every value in column $c$ , then set all of column $c$ to 0.

Write a program that reports the result of each query in order.

Input

The first line has the grid size $n$ and the number of queries $q$ ( $1 \le n \le 10^6$ , $1 \le q \le 10^5$ ).

Each of the next $q$ lines has one query, either R r ( $1 \le r \le n$ ) or C c ( $1 \le c \le n$ ).

Output

Print the result of the $i$ -th query on the $i$ -th line ( $1 \le i \le q$ ).

Examples5

Example 1

Input

3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3

Expected output

Example 2
Input
```
1 3
R 1
C 1
R 1
```
Expected output
```
2
0
0
```
Example 3
Input
```
2 4
C 1
R 1
C 2
R 2
```
Expected output
```
5
3
4
0
```

Example 4

Input

4 8
R 1
R 2
R 3
R 4
C 1
C 2
C 3
C 4

Expected output

Example 5

Input

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

Expected output