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)(0,0,0)$ to $(N,N,N)(N,\; N,\; N)$ ($2\le N\le 10002\; \backslash leq\; N\; \backslash leq\; 1000$). Farmer John will perform a series of $QQ$ ($1\le Q\le 2\cdot {10}^{5}1\; \backslash leq\; Q\; \backslash leq\; 2\; \backslash cdot\; 10^5$) update operations to his cheese block.

For each update operation, FJ will carve out the $11$ by $11$ by $11$ block of cheese extending from integer coordinates $(x,y,z)(x,\; y,\; z)$ to $(x+1,y+1,z+1)(x+1,\; y+1,\; z+1)$, where . It is guaranteed that there will exist a $11$ by $11$ by $11$ block of cheese at the location FJ carves. Since FJ is playing Moocraft, gravity does not cause parts of the cheese to fall if cheese below is carved.

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

입력

The first line contains $NN$ and $QQ$.

The following $QQ$ lines contain $xx$, $yy$, and $zz$, the coordinates to be carved.

출력

After each update operation, output an integer, the number of configurations.

힌트

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

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

0
0
1
2
5