농부 존은 정육면체 모양의 치즈 덩어리를 가지고 있다. 이 치즈는 3차원 좌표 공간에서 \((0,0,0)\)부터 \((N,N,N)\)까지 놓여 있다. (\(2\le N\le 1000\)) 농부 존은 치즈 덩어리에 \(Q\)번의 갱신 연산을 수행한다. (\(1\le Q\le 2\cdot 10^5\))

각 갱신 연산에서 농부 존은 정수 좌표 \((x,y,z)\)부터 \((x+1,y+1,z+1)\)까지 놓인 \(1\times 1\times 1\) 크기의 치즈 조각을 파낸다. 이때 \(0\le x,y,z<N\)이다. 농부 존이 파내려는 위치에는 항상 \(1\times 1\times 1\) 크기의 치즈 조각이 남아 있음이 보장된다. 농부 존은 무크래프트를 하고 있으므로, 아래쪽 치즈를 파내더라도 중력 때문에 치즈의 일부가 떨어지지는 않는다.

각 갱신 연산이 끝난 뒤, 남아 있는 치즈와 어떤 부분도 겹치지 않도록 \(1\times 1\times N\) 크기의 벽돌을 치즈 덩어리 안에 넣는 서로 다른 배치의 수를 출력하여라. 벽돌의 모든 꼭짓점은 세 좌표축 모두에서 \([0,N]\) 범위의 정수 좌표를 가져야 한다. 농부 존은 벽돌을 원하는 방향으로 회전할 수 있다.

입력

첫째 줄에 \(N\)과 \(Q\)가 공백으로 구분되어 주어진다.

다음 \(Q\)개의 줄에 파낼 치즈 조각의 좌표 \(x\), \(y\), \(z\)가 공백으로 구분되어 주어진다.

출력

각 갱신 연산이 끝난 뒤, 가능한 벽돌 배치의 수를 나타내는 정수 하나를 출력한다.

예제 입력

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

예제 출력

0
0
1
2
5

처음 세 번의 갱신 연산이 끝난 뒤, \([0,1]\times[0,2]\times[0,1]\) 영역을 차지하는 \(1\times 2\times 1\) 크기의 벽돌은 남아 있는 치즈와 겹치지 않는다. 따라서 이 배치는 답에 포함된다.

서브태스크

출처

USACO 2024 December Contest, Bronze, Problem 2. Farmer John's Cheese Block