Miếng bít tết là ma trận \(n\times n\), ban đầu mọi nhiệt độ bằng \(0\). Có \(q\) lần nướng. Với thao tác D x (\(x\le n\)), hàng \(n\) tăng \(x\), hàng \(n-1\) tăng \(x-1\), ..., hàng \(n-x+1\) tăng \(1\). Với L x hoặc R x (\(x\le\lfloor(n+1)/2\rfloor\)), các cột gần cạnh trái hoặc phải tương ứng tăng theo cùng quy luật: cột sát cạnh tăng \(x\), rồi giảm dần đến \(1\). Hãy tìm hiệu giữa nhiệt độ lớn nhất và nhỏ nhất sau tất cả thao tác.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n\le10^9\), \(1\le q\le10^5\)). Mỗi trong \(q\) dòng sau chứa ký tự L, R hoặc D và số \(x\) hợp lệ theo mô tả.

Dữ liệu ra

In hiệu giữa nhiệt độ lớn nhất và nhỏ nhất.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(7\) điểm: \(n,q\le20\).
2. \(22\) điểm: \(n,q\le1000\).
3. \(31\) điểm: \(n\le1000\).
4. \(6\) điểm: \(n\) chẵn.
5. \(4\) điểm: không có ràng buộc thêm.

Ví dụ

4 2
L 2
R 1

2

3 3
R 2
D 3
R 2

6

Nguồn

COCI 2025/2026 - Vòng 4, bài Tomahawk.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.