У Фермера Джона есть блок сыра в форме куба. Он лежит в трёхмерном пространстве
от точки \((0,0,0)\) до точки \((N, N, N)\) (\(2 \leq N \leq 1000\)). ФД выполняет серию
из \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) операций над своим блоком сыра.
В каждой операции ФД вырезает блок размером \(1\) * \(1\) * \(1\) из сыра от целых
координат \((x, y, z)\) до \((x+1, y+1, z+1)\), где \(0\le x,y,z<N\). Гарантируется,
сыр есть в этом месте. Поскольку ФД играет в Moocraft гравитация не вызывает падение
блоков сыра при вырезании.
После каждой операции выведите количество различных способов, которыми ФД
может вставить блок \(1\) * \(1\) * \(N\) так, что ни одна часть блока не перекрывается
с оставшимся сыром. Каждая вершина блока должна иметь целочисленные координаты
в интервале \([0,N]\) по всем трём осям. ФД может вращать блок как он хочет.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит \(N\) и \(Q\).
Последующие \(Q\) строк содержат \(x\), \(y\), \(z\), координаты вырезания.
ФОРМАТ ВЫВОДА (на экран / stdout):
После каждой операции выведите целое число - количество способов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0
|
0
0
1
2
5
|