Người đầu bếp tại nhà hàng nổi tiếng nhất ở đất cố đô đang chuẩn bị những miếng thịt bò Kobe cho một nhóm lập trình viên trẻ tuổi, vui vẻ và hiện đang rất đói.

Miếng thị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 thịt là ~0~ độ. Trong quá trình nấu, nhiệt độ ở các phần khác nhau của miếng thịt (tức là các ô khác nhau trong ma trận) sẽ tăng lên.

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

Khi miếng thịt được nướng ở cạnh dưới, nó có thể được nướng 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 thứ ~n-x+1~ sẽ tăng thêm ~1~.

Khi miếng thịt được nướng ở cạnh phải, nó có thể được nướng tối đa ~\left\lfloor\dfrac{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 thứ ~n-x+1~ sẽ tăng thêm ~1~.

Tương tự, khi miếng thịt được nướng ở cạnh trái, nó có thể được nướng tối đa ~\left\lfloor\dfrac{n+1}{2}\right\rfloor~ giây. Sau đó, nhiệt độ của tất cả các ô ở cột thứ nhất 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 thứ ~x~ sẽ tăng thêm ~1~.

Chúng ta biết rằng độ ngon của miếng bò Kobe có liên quan chặt chẽ đến sự chênh lệch nhiệt độ, vì vậy đầu bếp muốn tìm hiệu giữa phần lạnh nhất và phần nóng nhất của miếng thịt!

Input

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

• Trong mỗi dòng trong ~q~ dòng tiếp theo, có một ký tự ~s~ và một số tự nhiên ~x~. Ký tự ~s~ chỉ cạnh của miếng thịt bò Kobe: "L" - trái, "R" - phải, "D" - dưới. Nếu ~s~ = "D" thì ~1 \le x \le n~. Ngược lại, ~1 \le x \le \left\lfloor\dfrac{n+1}{2}\right\rfloor~.

Output

In ra một số duy nhất - là hiệu (đơn vị độ) giữa ô có nhiệt độ thấp nhất và ô có nhiệt độ cao nhất trên miếng thị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

Các bước tăng nhiệt độ trong ví dụ ~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}~

Các bước tăng nhiệt độ trong ví dụ ~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}~