Băng Chuyền 2D

Farmer John vận hành một nhà máy với lưới $N\times N$ chứa các băng chuyền. Mỗi ô chứa một trong năm loại:

• L, R, U, D: băng chuyền di chuyển vật phẩm sang trái, phải, lên, xuống tương ứng
• ?: ô chưa xây

Một ô được gọi là không sử dụng được nếu vật phẩm đặt tại đó sẽ lặp mãi mãi mà không thoát ra khỏi lưới.

Ban đầu tất cả ô đều là ?. Trong $Q$ ngày, mỗi ngày FJ xây một băng chuyền. Sau mỗi ngày, xác định số ô không sử dụng được tối thiểu có thể đạt được bằng cách điền tối ưu các ô ? còn lại.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $Q$ ($1\le N\le 1000$, $1\le Q\le 2·{10}^5$).
• $Q$ dòng tiếp theo: $r_i$, $c_i$, $t_i$ (hàng, cột, loại băng chuyền).

Dữ liệu ra

• $Q$ dòng, mỗi dòng chứa số ô không sử dụng được tối thiểu sau mỗi ngày.

Ràng buộc

• Test $2$-$4$: $N\le 40$
• Test $5$-$13$: Không có ràng buộc thêm

Ví dụ