You are provided with a square grid of side length $N$. The grid contains numbers from $1$ to $N \times N$, arranged sequentially from left to right and top to bottom across the rows. Your task is to compute and display the sum of the numbers in a specific row or column, based on the given input.

Here's an example with $N=3$. The sum of row $1$ is $6$, and the sum of column $3$ is $18$.

Input

The first line of input consists of two integers, $N$ and $Q$, where $Q$ is the number of queries that follow.
Each query consists of a character, either R (for row) or C (for column), followed by an integer $X$, indicating the row or column number to be summed.

Output

For each query, output the sum of the numbers in the specified row or column.

Constraints

For all cases: $1 \le N \le 10^6$, $1 \le Q \le 10^5$, $1 \le X \le N$
Subtask 1 (5%): $N = 1$
Subtask 2 (15%): $1 \le N \le 4$
Subtask 3 (20%): $1 \le N \le 10^3$
Subtask 4 (15%): Only R queries are present
Subtask 5 (15%): Only C queries are present
Subtask 6 (30%): No additional constraints