Farmer John의 치즈 블록

Farmer John에게 정육면체 모양의 치즈 덩어리가 있다. 이 치즈는 3차원 좌표 평면 위에 놓여 있으며 $(0,0,0)$부터 $(N, N, N)$까지 뻗어 있다 ($2 \leq N \leq 1000$). Farmer John은 이 치즈 덩어리에 $Q$번 ($1 \leq Q \leq 2 \cdot 10^5$)의 갱신 작업을 수행한다.

각 갱신 작업마다 FJ는 정수 좌표 $(x, y, z)$부터 $(x+1, y+1, z+1)$까지 뻗은 $1 \times 1 \times 1$ 크기의 치즈 조각을 파낸다. 여기서 $0 \leq x, y, z < N$이다. FJ가 파내는 위치에는 항상 $1 \times 1 \times 1$ 크기의 치즈가 있다고 보장된다. FJ는 Moocraft를 하고 있으므로, 아래쪽 치즈를 파내도 중력 때문에 위의 치즈가 떨어지지 않는다.

각 갱신 후에, FJ가 $1 \times 1 \times N$ 크기의 막대를 치즈 덩어리에 꽂을 수 있는 서로 다른 배치의 수를 구한다. 막대의 어떤 부분도 남아 있는 치즈와 겹치면 안 된다. 막대의 모든 꼭짓점은 세 축 모두에서 $[0, N]$ 범위의 정수 좌표를 가져야 한다. FJ는 막대를 원하는 대로 회전시킬 수 있다.

첫 줄에 $N$과 $Q$가 주어진다.

다음 $Q$개의 줄에는 파낼 좌표 $x$, $y$, $z$가 각각 주어진다.

각 갱신 후에 배치의 수를 정수 하나로 출력한다.

처음 세 번의 갱신 후, $[0, 1] \times [0, 2] \times [0, 1]$ 범위에 걸친 $1 \times 2 \times 1$ 막대는 남은 치즈와 겹치지 않으므로 답에 포함된다.