RoAlgo Contest #9 | Lucky Sudoku

Task

JellyTheOctopus is ready to play today's New York Times Sudoku! Just for him, the sudoku setters have added a new difficulty "Impossible", to the normal "Easy", "Medium" and "Hard".

The rules of normal Sudoku are as follows: you are given a $9$ x $9$ grid, split into $9 \ 3$ x $3$ boxes. Place the digits $1$ through $9$ each in every row, column, and box such that each digit appears only once. However, in today's new difficulty, there are a few minor changes. Instead of a $9$ x $9$ grid, there is a $N$ x $N$ grid, split into many $3$ x $3$ boxes ($N$ is a multiple of $3$).

Due to the nature of these new grid sizes, some digits might already have repeats (in a column or row). However, any new digits added by Jelly must still follow normal sudoku rules (E.g. if there are three ones in a column, Jelly cannot place another one in that column). You can see here a picture of a normal sudoku grid.

As the name suggests, it is very likely that this puzzle is impossible to solve. Thus, Jelly has created a new challenge for himself. As we all know, $8$ is the luckiest number, and Jelly wants to find the "luckiness" of the grid. Given an $N$ x $N$ grid, find all positions where Jelly can place a single $8$.

Jelly will only write a single digit. If he places an $8$ in another position, he will erase it off the grid before considering other positions that he can place an $8$ at.

The luckiness of the grid is calculated as the number of positions he can place a single $8$ at. Help Jelly find this number before NYT publishes their next Impossible Sudoku Puzzle!

Input data

In the first line you are given an integer $N$ and $M$, the number of places already filled.

On the next line you are given the coordinates where we already placed digits, together with the digit we placed.

Output data

The output will contain the luckiness of the grid Jelly received as part of today's Impossible New York Times Sudoku Puzzle.

Constraints and clarifications

• $3 \leq N \leq 2 \cdot 10^5$;
• $N$ is a multiple of $3$;
• $0 \leq M \leq \min(2 \cdot 10^5, N^2)$;
• $0 \leq x, y < N$;
• $1 \leq digit \leq 9$;

Example

stdin

9 7
1 7 8
3 2 1
4 7 3
1 0 5
8 7 4
2 4 9
3 4 6

stdout

57

Explanation

In the example grid, he can't place a $8$ on any of the squares already filled, as well as on any of the squares on line $1$ and column $7$.