Viruses

We have an $n \times n$ board whose cells are indexed by pairs of integers $(x, y)$ with $1 \le x, y \le n$; the cell $(1, 1)$ is in the bottom-left corner. Every cell starts empty. As time passes, viruses of several kinds appear on the board and begin to multiply.

Each virus has a fixed appearance time, given as a day and an hour, together with a fixed appearance cell $(x, y)$. When a virus's appearance moment arrives it occupies its appearance cell, as long as that cell is still empty. If the cell is already occupied by another virus, then this virus never appears and occupies nothing.

From then on, on every following day at the same hour, the virus activates and replicates: every still-empty cell that is adjacent to a cell already held by this virus becomes occupied by that virus. Two cells $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent when $\max(|x_2 - x_1|, |y_2 - y_1|) = 1$ (that is, each of the eight surrounding cells). The viruses keep replicating day after day until the whole board is occupied.

Every virus has a distinct hour of appearance, so within any single day the viruses act one after another in increasing order of their hour. Because of this, the virus that ends up owning each cell is determined without ambiguity.

Write a program that reads the description of the viruses and, for each virus, reports how many cells it occupies once the board has been completely filled.

The first line contains two integers $n$ and $k$ separated by a single space, where $1 \le n \le 1000000$ and $1 \le k \le 24$.

Each of the next $k$ lines contains four integers $h$, $d$, $x$ and $y$ separated by single spaces, where $0 \le h \le 23$ and $1 \le d, x, y \le n$. They are, respectively, the hour, the day, and the coordinates of one virus's appearance. No two viruses share the same hour $h$.

Print $k$ integers, one per line. The $i$-th line holds the number of cells occupied by the $i$-th virus (in the input order) once the board is full. A virus that never appears occupies $0$ cells.

In the first sample the table below shows, for each cell, the day on which it became occupied. The rows are drawn so that cell $(1, 1)$ is in the bottom-left corner (the top row is $y = 5$ and the bottom row is $y = 1$), while columns go from $x = 1$ on the left to $x = 5$ on the right.

The virus scheduled to appear at $(3, 3)$ on day $3$ finds that cell already taken, so it never appears and occupies $0$ cells.