Khối Phô Mai Của FJ

Farmer John có một khối phô mai hình lập phương nằm trong hệ tọa độ 3 chiều, kéo dài từ $(0,0,0)$ đến $(N,N,N)$ với $2\le N\le 1000$. FJ thực hiện $Q$ thao tác cắt ($1\le Q\le 2·{10}^5$), mỗi thao tác loại bỏ một khối phô mai đơn vị $1\times 1\times 1$ tại tọa độ $(x,y,z)$ đến $(x+1,y+1,z+1)$ với $0\le x,y,z<N$.

Sau mỗi thao tác cắt, đếm số cách đặt một viên gạch $1\times 1\times N$ sao cho viên gạch không chồng lên phô mai còn lại. Viên gạch có thể xoay theo các trục và mọi đỉnh phải có tọa độ nguyên trong khoảng $[0,N]$ cho cả ba trục.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $Q$.
• $Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x$, $y$, $z$ - tọa độ khối cần cắt.

Dữ liệu ra

Sau mỗi thao tác cắt, in ra một số nguyên - số cách đặt viên gạch hợp lệ.

Ràng buộc

• Test $2$-$4$: $N\le 10$, $Q\le 1000$
• Test $5$-$7$: $N\le 100$, $Q\le 1000$
• Test $8$-$16$: Không có ràng buộc thêm

Ví dụ