波兰最著名餐厅的主厨正在为一群年轻、开朗（且非常饥饿）的程序员准备战斧牛排！

牛排可以用一个 $n \times n$ 的矩阵来表示。最初，整个牛排的温度都是 $0$ 度。在烹饪过程中，牛排不同部分（即矩阵中的不同格子）的温度会升高。

为了制作出完美的战斧牛排，主厨会将牛排拿起并重新放回烤架上 $q$ 次。每次，主厨可以将牛排放在以下三个侧面之一：左侧、右侧或下侧。然后，他会让牛排在该侧面烤 $x$ 秒。

当牛排在下侧烘烤时，最多可以烤 $n$ 秒。此后，矩阵中第 $n$ 行所有格子的温度将增加 $x$，第 $n - 1$ 行格子的温度将增加 $x - 1$，第 $n - 2$ 行格子的温度将增加 $x - 2$，……，第 $n - x + 1$ 行格子的温度将增加 $1$。

当战斧牛排在右侧烘烤时，最多可以烤 $\lfloor \frac{n+1}{2} \rfloor$ 秒。此后，矩阵中第 $n$ 列所有格子的温度将增加 $x$，第 $n - 1$ 列格子的温度将增加 $x - 1$，第 $n - 2$ 列格子的温度将增加 $x - 2$，……，第 $n - x + 1$ 列格子的温度将增加 $1$。

类似地，当战斧牛排在左侧烘烤时，最多可以烤 $\lfloor \frac{n+1}{2} \rfloor$ 秒。此后，矩阵中第一列所有格子的温度将增加 $x$，第二列格子的温度将增加 $x - 1$，第三列格子的温度将增加 $x - 2$，……，第 $x$ 列格子的温度将增加 $1$。

我们知道，战斧牛排的美味程度与温度的对比密切相关，这就是为什么主厨想要找出牛排最冷和最热部分之间的温度差！

输入格式

第一行包含两个自然数 $n$ 和 $q$（$1 \le n \le 10^9$，$1 \le q \le 10^5$），分别表示牛排的大小和主厨拿起牛排的次数。

接下来的 $q$ 行中，每行包含一个字母 $s$ 和一个自然数 $x$。字母 $s$ 表示战斧牛排的侧面：L 表示左侧，R 表示右侧，D 表示下侧。如果 $s = \text{"D"}$，则 $1 \le x \le n$。否则，$1 \le x \le \lfloor \frac{n+1}{2} \rfloor$。

输出格式

在第一行也是唯一一行中，输出一个整数，表示牛排上最冷和最热格子之间的温度差。

子任务

样例

输入样例 1

4 2
L 2
R 1

输出样例 1

2

输入样例 2

3 3
R 2
D 3
R 2

输出样例 2

6

样例 1 说明

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

样例 2 说明

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