CF131E.Yet Another Task with Queens

A queen is the strongest chess piece. In modern chess the queen can move any number of squares in any horizontal, vertical or diagonal direction (considering that there're no other pieces on its way). The queen combines the options given to the rook and the bishop.

There are m queens on a square n × n chessboard. You know each queen's positions, the i-th queen is positioned in the square (r__i, c__i), where r__i is the board row number (numbered from the top to the bottom from 1 to n), and c__i is the board's column number (numbered from the left to the right from 1 to n). No two queens share the same position.

For each queen one can count w — the number of other queens that the given queen threatens (attacks). For a fixed attack direction only the first queen in this direction is under attack if there are many queens are on the ray of the attack. Obviously, for any queen w is between 0 and 8, inclusive.

Print the sequence _t_0, _t_1, ..., _t_8, where t__i is the number of queens that threaten exactly i other queens, i.e. the number of queens that their w equals i.

皇后是国际象棋中威力最强的棋子。在现代国际象棋中，皇后可以沿任意水平、垂直或对角线方向移动任意格数（前提是其行进路径上没有其他棋子阻挡）。皇后的走法融合了车（rook）和象（bishop）的所有走法。

在一个 $n \times n$ 的方形棋盘上有 $m$ 个皇后。已知每个皇后的位置：第 $i$ 个皇后位于格子 $(r_i,\,c_i)$，其中 $r_i$ 表示棋盘的行号（从上到下编号为 $1$ 到 $n$），$c_i$ 表示棋盘的列号（从左到右编号为 $1$ 到 $n$）。任意两个皇后均不占据同一位置。

对每个皇后，可计算其威胁（即攻击）的其他皇后数量 $w$。在某一固定攻击方向上，若该方向射线上存在多个皇后，则仅最靠近当前皇后的那个皇后被视为被攻击（即只计第一个）。显然，对任意皇后，$w$ 的取值范围为 $0$ 到 $8$（含端点）。

请输出序列 $t_0,\,t_1,\,\dots,\,t_8$，其中 $t_i$ 表示恰好威胁 $i$ 个其他皇后的皇后数量，即满足 $w = i$ 的皇后个数。

The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 105), where n is the size of the board and m is the number of queens on the board. Then m following lines contain positions of the queens, one per line. Each line contains a pair of integers r__i, c__i (1 ≤ r__i, c__i ≤ n) — the queen's position. No two queens stand on the same square.

输入的第一行包含一对整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），其中 $n$ 表示棋盘的大小，$m$ 表示棋盘上皇后的数量。接下来的 $m$ 行每行描述一个皇后的位置。每行包含一对整数 $r_i$、$c_i$（$1 \leq r_i, c_i \leq n$），表示该皇后的位置。任意两个皇后均不位于同一格子上。

Print the required sequence _t_0, _t_1, ..., _t_8, separating the numbers with spaces.

输出所需的序列 $t_0,\ t_1,\ \dots,\ t_8$，数字之间用空格分隔。