Farmer John's Cheese Block

Farmer John has a block of cheese in the shape of a cube. It lies on the 3-dimensional coordinate plane, extending from $(0,0,0)$ to $(N, N, N)$ ($2 \leq N \leq 1000$). Farmer John will perform a series of $Q$ ($1 \leq Q \leq 2 \cdot 10^5$) update operations to his cheese block.

For each update operation, FJ carves out the $1 \times 1 \times 1$ block of cheese extending from integer coordinates $(x, y, z)$ to $(x+1, y+1, z+1)$, where $0 \leq x, y, z < N$. It is guaranteed that a $1 \times 1 \times 1$ block of cheese exists at the location FJ carves. Since FJ is playing Moocraft, gravity does not cause parts of the cheese to fall if the cheese below is carved.

After each update, output the number of distinct configurations in which FJ can stick a $1 \times 1 \times N$ brick into the cheese block such that no part of the brick overlaps any remaining cheese. Every vertex of the brick must have integer coordinates in the range $[0, N]$ on all three axes. FJ may rotate the brick however he wants.

The first line contains $N$ and $Q$.

Each of the following $Q$ lines contains $x$, $y$, and $z$, the coordinates to carve.

After each update, output one integer: the number of configurations.

After the first three updates, the $1 \times 2 \times 1$ brick spanning $[0, 1] \times [0, 2] \times [0, 1]$ does not overlap the remaining cheese, so it contributes to the answer.