Farmer John có một khối phô mai hình lập phương. Khối phô mai nằm trong không gian tọa độ ba chiều, trải từ \((0,0,0)\) đến \((N,N,N)\) (\(2\leq N\leq 1000\)). Farmer John sẽ thực hiện một chuỗi \(Q\) (\(1\leq Q\leq 2\cdot 10^5\)) thao tác cập nhật trên khối phô mai.

Trong mỗi thao tác cập nhật, FJ sẽ khoét bỏ khối phô mai kích thước \(1\times 1\times 1\) trải từ tọa độ nguyên \((x,y,z)\) đến \((x+1,y+1,z+1)\), trong đó \(0\leq x,y,z<N\). Đảm bảo tại vị trí FJ khoét luôn tồn tại một khối phô mai \(1\times 1\times 1\). Vì FJ đang chơi Moocraft, trọng lực không khiến các phần phô mai rơi xuống khi phần phô mai bên dưới bị khoét bỏ.

Sau mỗi lần cập nhật, hãy in số cấu hình khác nhau mà FJ có thể đặt một viên gạch kích thước \(1\times 1\times N\) vào khối phô mai sao cho không phần nào của viên gạch chồng lên phần phô mai còn lại. Mọi đỉnh của viên gạch phải có tọa độ nguyên thuộc đoạn \([0,N]\) trên cả ba trục. FJ có thể xoay viên gạch theo bất kỳ cách nào.

Dữ liệu vào

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

\(Q\) dòng tiếp theo chứa \(x\), \(y\) và \(z\), là tọa độ cần khoét.

Dữ liệu ra

Sau mỗi thao tác cập nhật, in ra một số nguyên là số cấu hình.

Phân nhóm

• Các test 2–4: \(N\leq 10\) và \(Q\leq 1000\).
• Các test 5–7: \(N\leq 100\) và \(Q\leq 1000\).
• Các test 8–16: Không có ràng buộc bổ sung.

Ví dụ

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0

0
0
1
2
5

Nguồn

Đề bài gốc: USACO 2024 December Contest, Bronze — Farmer John's Cheese Block

Tác giả: Chongtian Ma, Alex Liang.