Đầu bếp tại nhà hàng nổi tiếng nhất Ba Lan đang chuẩn bị các miếng bít tết tomahawk cho một nhóm các lập trình viên trẻ tuổi, vui vẻ (và rất đói)!

Miếng bít tết có thể được biểu diễn dưới dạng một ma trận ~n \times n~. Ban đầu, nhiệt độ của toàn bộ miếng bít tết là ~0~ độ. Trong quá trình nấu, nhiệt độ ở các phần khác nhau của miếng bít tết (tức là các ô khác nhau trong ma trận) sẽ tăng lên.

Để chuẩn bị một miếng bít tết tomahawk hoàn hảo, đầu bếp nhấc miếng bít tết lên và đặt nó trở lại vỉ nướng ~q~ lần. Mỗi lần, đầu bếp có thể đặt miếng bít tết lên một trong ba mặt: trái, phải, hoặc dưới. Sau đó, anh ấy sẽ để miếng bít tết nấu trên mặt đó trong ~x~ giây.

Khi miếng bít tết được nướng ở mặt dưới, nó có thể được nướng trong tối đa ~n~ giây. Sau đó, nhiệt độ của tất cả các ô ở hàng thứ ~n~ trong ma trận sẽ tăng thêm ~x~, nhiệt độ của các ô ở hàng thứ ~n - 1~ sẽ tăng thêm ~x - 1~, nhiệt độ của các ô ở hàng thứ ~n - 2~ sẽ tăng thêm ~x - 2~, ~\dots~, nhiệt độ của các ô ở hàng số ~n - x + 1~ sẽ tăng thêm ~1~.

Khi miếng bít tết tomahawk được nướng ở mặt phải, nó có thể được nướng trong tối đa ~\left\lfloor \frac{n+1}{2} \right\rfloor~ giây. Sau đó, nhiệt độ của tất cả các ô ở cột thứ ~n~ trong ma trận sẽ tăng thêm ~x~, nhiệt độ của các ô ở cột thứ ~n - 1~ sẽ tăng thêm ~x - 1~, nhiệt độ của các ô ở cột thứ ~n - 2~ sẽ tăng thêm ~x - 2~, ~\dots~, nhiệt độ của các ô ở cột số ~n - x + 1~ sẽ tăng thêm ~1~.

Tương tự, khi miếng bít tết tomahawk được nướng ở mặt trái, nó có thể được nướng trong tối đa ~\left\lfloor \frac{n+1}{2} \right\rfloor~ giây. Sau đó, nhiệt độ của tất cả các ô ở cột đầu tiên trong ma trận sẽ tăng thêm ~x~, nhiệt độ của các ô ở cột thứ hai sẽ tăng thêm ~x - 1~, nhiệt độ của các ô ở cột thứ ba sẽ tăng thêm ~x - 2~, ~\dots~, nhiệt độ của các ô ở cột số ~x~ sẽ tăng thêm ~1~.

Chúng ta biết rằng độ ngon của miếng tomahawk liên quan chặt chẽ đến sự tương phản về nhiệt độ, đó là lý do tại sao đầu bếp muốn tìm ra sự chênh lệch giữa phần lạnh nhất và phần nóng nhất của miếng bít tết!

Input

Trong dòng đầu tiên, có hai số tự nhiên ~n~ và ~q~ ~(1 \le n \le 10^5,\ 1 \le q \le 10^5)~, kích thước của miếng bít tết và số lần đầu bếp nhấc miếng bít tết lên.

Trong mỗi dòng trong ~q~ dòng tiếp theo, có một chữ cái đơn ~s~ và một số tự nhiên ~x~. Chữ cái ~s~ cho biết mặt của miếng bít tết tomahawk: "L" - trái, "R" - phải, hoặc "D" - dưới. Nếu ~s =~ "D", thì ~1 \le x \le n~. Ngược lại, ~1 \le x \le \left\lfloor \frac{n+1}{2} \right\rfloor~.

Output

Trong dòng đầu tiên và duy nhất, in ra một số duy nhất - sự chênh lệch về độ giữa ô lạnh nhất và ô nóng nhất trên miếng bít tết.

Scoring

Sample Input 1

4 2
L 2
R 1

Sample Output 1

2

Sample Input 2

3 3
R 2
D 3
R 2

Sample Output 2

6

Notes

Giải thích test thứ nhất:

~\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}~

Giải thích test thứ hai:

~\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}~