Đầu bếp của nhà hàng nổi tiếng nhất Ba Lan đang chuẩn bị món bít tết tomahawk cho một nhóm lập trình viên trẻ trung, vui vẻ và cực kỳ đói.

Miếng bít tết được mô tả bởi một ma trận ~n \times n~. Ban đầu, nhiệt độ của toàn bộ miếng thịt đều bằng ~0~ độ. Trong quá trình nướng, nhiệt độ ở các phần khác nhau của miếng thịt, tức các ô khác nhau trong ma trận, sẽ tăng lên.

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

Nếu miếng thịt được nướng ở cạnh dưới thì thời gian nướng tối đa là ~n~ giây. Khi đó, toàn bộ các ô ở hàng ~n~ tăng thêm ~x~, các ô ở hàng ~n-1~ tăng thêm ~x-1~, các ô ở hàng ~n-2~ tăng thêm ~x-2~, ..., và các ô ở hàng ~n-x+1~ tăng thêm ~1~.

Nếu miếng thịt được nướng ở cạnh phải thì thời gian nướng tối đa là ~\left\lfloor \frac{n+1}{2} \right\rfloor~ giây. Khi đó, toàn bộ các ô ở cột ~n~ tăng thêm ~x~, các ô ở cột ~n-1~ tăng thêm ~x-1~, các ô ở cột ~n-2~ tăng thêm ~x-2~, ..., và các ô ở cột ~n-x+1~ tăng thêm ~1~.

Tương tự, nếu miếng thịt được nướng ở cạnh trái thì thời gian nướng tối đa cũng là ~\left\lfloor \frac{n+1}{2} \right\rfloor~ giây. Khi đó, toàn bộ các ô ở cột ~1~ tăng thêm ~x~, các ô ở cột ~2~ tăng thêm ~x-1~, các ô ở cột ~3~ tăng thêm ~x-2~, ..., và các ô ở cột ~x~ tăng thêm ~1~.

Ta biết rằng độ ngon của miếng tomahawk phụ thuộc chặt chẽ vào độ tương phản nhiệt độ, vì vậy đầu bếp muốn biết chênh lệch 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ố nguyên dương ~n~ và ~q~: kích thước của miếng thịt và số lần đầu bếp nhấc miếng thịt lên.

Mỗi trong ~q~ dòng tiếp theo chứa một ký tự ~s~ và một số nguyên dương ~x~. Ký tự ~s~ cho biết cạnh được đặt lên vỉ:

• ~\texttt{L}~: cạnh trái
• ~\texttt{R}~: cạnh phải
• ~\texttt{D}~: cạnh dưới

Nếu ~s = \texttt{D}~ thì ~x~ là thời gian nướng ở cạnh dưới. Ngược lại, ~x~ là thời gian nướng ở cạnh trái hoặc phải.

Output

In ra trên một dòng duy nhất hiệu giữa nhiệt độ lớn nhất và nhiệt độ nhỏ nhất của một ô trên miếng thịt.

Ràng buộc

• ~1 \le n \le 10^9~
• ~1 \le q \le 10^5~
• Nếu ~s = \texttt{D}~ thì ~1 \le x \le n~
• Nếu ~s \in \{\texttt{L}, \texttt{R}\}~ thì ~1 \le x \le \left\lfloor \frac{n+1}{2} \right\rfloor~

Chấm điểm

• Subtask 1 (7 điểm): ~n, q \le 20~
• Subtask 2 (22 điểm): ~n, q \le 1000~
• Subtask 3 (31 điểm): ~n \le 1000~
• Subtask 4 (6 điểm): ~n~ là số chẵn
• Subtask 5 (4 điểm): Không có ràng buộc bổ sung.

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

Giải thích

• Ví dụ 1: Sau thao tác ~\texttt{L }2~, cột ~1~ tăng thêm ~2~ và cột ~2~ tăng thêm ~1~. Sau thao tác ~\texttt{R }1~, cột cuối tăng thêm ~1~. Khi đó nhiệt độ nhỏ nhất là ~0~, lớn nhất là ~2~, nên đáp án là ~2~.