Nhà máy sữa của Farmer John có thể được mô tả bằng một lưới ô vuông \(N\times N\) (\(1\leq N\leq 1000\)) chứa các băng chuyền. Vị trí \((a,b)\) chỉ ô ở hàng thứ \(a\) tính từ trên xuống và cột thứ \(b\) tính từ trái sang. Có \(5\) loại ô:

1. L — băng chuyền hướng sang trái, di chuyển mọi vật trên nó sang trái \(1\) ô sau mỗi đơn vị thời gian.
2. R — băng chuyền hướng sang phải, di chuyển mọi vật trên nó sang phải \(1\) ô sau mỗi đơn vị thời gian.
3. U — băng chuyền hướng lên trên, di chuyển mọi vật trên nó lên trên \(1\) ô sau mỗi đơn vị thời gian.
4. D — băng chuyền hướng xuống dưới, di chuyển mọi vật trên nó xuống dưới \(1\) ô sau mỗi đơn vị thời gian.
5. ? — Farmer John chưa xây băng chuyền tại ô đó.

Lưu ý rằng băng chuyền cũng có thể đưa vật ra ngoài lưới. Một ô \(c\) là không sử dụng được nếu một vật được đặt tại ô \(c\) sẽ không bao giờ thoát khỏi lưới băng chuyền (tức là nó sẽ di chuyển mãi trong lưới).

Ban đầu Farmer John chưa bắt đầu xây nhà máy nên mọi ô đều là ?. Trong \(Q\) ngày tiếp theo (\(1\leq Q\leq 2\cdot 10^5\)), từ ngày \(1\) đến ngày \(Q\), Farmer John sẽ chọn một ô chưa có băng chuyền và xây một băng chuyền tại đó.

Cụ thể, trong ngày thứ \(i\), Farmer John xây một băng chuyền loại \(t_i\) (\(t_i\in\{\text{L,R,U,D}\}\)) tại vị trí \((r_i,c_i)\) (\(1\leq r_i,c_i\leq N\)). Đảm bảo vị trí \((r_i,c_i)\) chưa có băng chuyền.

Sau mỗi ngày, hãy giúp Farmer John tìm số ô không sử dụng được nhỏ nhất có thể đạt được bằng cách xây băng chuyền một cách tối ưu trên tất cả các ô còn lại chưa có băng chuyền.

Dữ liệu vào

Dòng đầu chứa \(N\) và \(Q\).

Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa lần lượt \(r_i\), \(c_i\) và \(t_i\).

Dữ liệu ra

In ra \(Q\) dòng, dòng thứ \(i\) mô tả số ô không sử dụng được nhỏ nhất nếu Farmer John xây băng chuyền tối ưu trên tất cả các ô còn lại hiện chưa có băng chuyền.

Phân nhóm

• Các test 4–5: \(N\leq 10\).
• Các test 6–7: \(N\leq 40\).
• Các test 8–13: Không có ràng buộc bổ sung.

Ví dụ

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

0
0
0
2
3

RL?
U??
?DL

RLR
URR
LDL

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

0
2
2
4
4
6
6
9

RLD
D?U
URL

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

0
0
0
0
0
0
0
0
11
11
11
11
13

Nguồn

Đề bài gốc: USACO 2024 December Contest, Silver — 2D Conveyor Belt

Tác giả: Alex Liang.