바이러스

$n \times n$ 크기의 판이 있고, 각 칸은 정수 쌍 $(x, y)$ ($1 \le x, y \le n$)로 나타냅니다. 칸 $(1, 1)$은 왼쪽 아래 모서리에 있습니다. 처음에 모든 칸은 비어 있습니다. 시간이 지나면서 여러 종류의 바이러스가 판 위에 나타나 번식하기 시작합니다.

각 바이러스에는 나타나는 시각이 일과 시로 정해져 있고, 나타나는 칸 $(x, y)$도 정해져 있습니다. 바이러스가 나타나는 순간이 되면, 그 칸이 아직 비어 있는 경우에 한해 해당 칸을 차지합니다. 만약 그 칸이 이미 다른 바이러스에게 점령되어 있다면, 이 바이러스는 아예 나타나지 않으며 어떤 칸도 차지하지 못합니다.

그 뒤로는 매일 같은 시각에 바이러스가 활성화되어 번식합니다. 번식이란 이 바이러스가 이미 차지한 칸과 인접하면서 아직 비어 있는 모든 칸을 이 바이러스가 새로 차지하는 것을 말합니다. 두 칸 $(x_1, y_1)$과 $(x_2, y_2)$는 $\max(|x_2 - x_1|, |y_2 - y_1|) = 1$일 때 인접합니다(즉 자신을 둘러싼 여덟 칸). 바이러스들은 판 전체가 점령될 때까지 날마다 계속 번식합니다.

모든 바이러스의 나타나는 시각(시)은 서로 다르므로, 같은 날 안에서는 시각이 작은 바이러스부터 차례대로 행동합니다. 따라서 각 칸을 최종적으로 차지하는 바이러스는 모호함 없이 결정됩니다.

바이러스들의 정보를 읽어, 판이 완전히 채워졌을 때 각 바이러스가 차지한 칸의 수를 구하는 프로그램을 작성하세요.

첫째 줄에 두 정수 $n$과 $k$가 공백 하나로 구분되어 주어집니다 ($1 \le n \le 1000000$, $1 \le k \le 24$).

다음 $k$개의 줄에는 각각 네 정수 $h$, $d$, $x$, $y$가 공백 하나로 구분되어 주어집니다 ($0 \le h \le 23$, $1 \le d, x, y \le n$). 이는 각각 한 바이러스가 나타나는 시각(시), 날, 그리고 좌표를 나타냅니다. 서로 다른 두 바이러스가 같은 시각 $h$를 갖는 경우는 없습니다.

$k$개의 정수를 한 줄에 하나씩 출력합니다. $i$번째 줄에는 입력 순서로 $i$번째 바이러스가 판이 다 채워졌을 때 차지한 칸의 수를 출력합니다. 한 번도 나타나지 못한 바이러스는 $0$을 출력합니다.

아래 표는 첫 번째 예제에서 각 칸이 점령된 날을 나타냅니다. 칸 $(1, 1)$이 왼쪽 아래 모서리에 오도록 그렸으므로, 맨 윗줄이 $y = 5$, 맨 아랫줄이 $y = 1$이고, 열은 왼쪽 $x = 1$부터 오른쪽 $x = 5$까지입니다.

$3$일에 $(3, 3)$에 나타날 예정이던 바이러스는 그 칸이 이미 점령된 것을 발견하므로, 나타나지 못하고 $0$개의 칸을 차지합니다.