Cheese Brick Insertion

Farmer John has a cubic block of cheese located in three-dimensional space with integer coordinates from \( (0,0,0) \) to \( (N,N,N) \) (where \(2 \le N \le 1000\)). Initially, the entire cheese is intact, meaning it is subdivided into \(N^3\) unit cubes. Farmer John will perform \(Q\) updates (\(1 \le Q \le 2\cdot10^5\)).

For each update, he removes a \(1\times 1\times 1\) cube from the cheese. Specifically, given an integer coordinate \((x,y,z)\) with \(0 \le x,y,z < N\), he removes the cube spanning from \((x,y,z)\) to \((x+1,y+1,z+1)\). It is guaranteed that the cube at the given position has not been removed before. Note that even if cubes below are removed, gravity does not cause any cheese above to fall.

After each update, output the number of ways to insert a \(1\times 1\times N\) brick into the cheese such that the brick does not overlap with any remaining cheese. The brick, which has dimensions \(1\times 1\times N\), may be rotated arbitrarily; however, the coordinates of every vertex of the brick must be an integer in the range \([0, N]\). Under these conditions, the only valid orientations are those aligned with the coordinate axes. Hence, the brick can only be placed along one of the three axes:

• X-axis: occupies all cells \((0,y,z), (1,y,z), \dots, (N-1,y,z)\) for some fixed \(y, z\).
• Y-axis: occupies cells \((x,0,z), (x,1,z), \dots, (x,N-1,z)\) for some fixed \(x, z\).
• Z-axis: occupies cells \((x,y,0), (x,y,1), \dots, (x,y,N-1)\) for some fixed \(x, y\).

A brick placement is valid if, in the corresponding line, all unit cubes have been removed from the cheese. Note that initially no brick can be inserted since the cheese is complete. You are to output the cumulative count of valid placements after each removal update.

Input and output example:

Input:
2 3
0 0 0
1 0 0
0 1 0
Output:
0
1
2

</p>

inputFormat

The first line contains two integers \(N\) and \(Q\) separated by a space.

Each of the following \(Q\) lines contains three integers \(x\), \(y\), and \(z\) representing the coordinates of the unit cube to be removed.

It is guaranteed that \(2 \le N \le 1000\) and \(1 \le Q \le 2 \cdot 10^5\), and that the cube at the given position exists (i.e. has not been previously removed).

outputFormat

After each removal operation, output a single line containing the total number of valid ways to insert the brick into the cheese such that it does not overlap with any remaining cheese.

sample

2 3
0 0 0
1 0 0
0 1 0

0
1
2

</p>