Problem Description

Consider an $n\times n$ matrix $A$. Initially, all elements in $A$ are zero.

Use the following conventions: rows are horizontal and columns are vertical. Rows are numbered from top to bottom as $1\sim n$, and columns are numbered from left to right as $1\sim n$.

There are $q$ operations:

• $\texttt{L}$ $x$: here, $1\le x\le \lfloor \frac{n+1}{2}\rfloor$.
  • For $i=1,\ldots,x$, add $(x-i+1)$ to every cell in column $i$.
• $\texttt{R}$ $x$: here, $1\le x\le \lfloor \frac{n+1}{2}\rfloor$.
  • For $i=1,\ldots,x$, add $(x-i+1)$ to every cell in column $(n-i+1)$.
• $\texttt{D}$ $x$: here, $1\le x\le n$.
  • For $i=1,\ldots,x$, add $(x-i+1)$ to every cell in row $(n-i+1)$.

After all operations, find the range of the matrix (the difference between the maximum value and the minimum value).

Input Format

The first line contains two positive integers $n,q$ ($1\le n\le 10^9$, $1\le q\le 10^5$).

The next $q$ lines each contain a character $s$ and a positive integer $x$, where $s\in \{\texttt{L},\texttt{R},\texttt{D}\}$.

• If $s=\texttt{D}$, then $1\le x\le n$;
• otherwise, $1\le x\le \lfloor \frac{n+1}{2}\rfloor$.

Output Format

Output one integer on a single line, representing the range (the difference between the maximum value and the minimum value).

4 2
L 2
R 1

2

3 3
R 2
D 3
R 2

6

Hint

Sample Explanation

Explanation for sample 1:

$\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 2 & 1 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 2 & 1 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \end{bmatrix}$

Explanation for sample 2:

$\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \\ 0 & 1 & 2 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 5 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \\ 3 & 5 & 7 \end{bmatrix}$

Subtasks

Translated by ChatGPT 5