← 返回题目列表

Codeforces · 131/E

E. 皇后区的另一项任务

中文机器翻译题面 查看原题

皇后是最强的棋子。在现代国际象棋中,皇后可以在任何水平、垂直或对角线方向移动任意数量的方格(考虑到路上没有其他棋子)。皇后结合了车和象的选项。

一个 n × n 的方格棋盘上有 m 个皇后。你知道每个皇后的位置,第 i 个皇后位于方格 (ri, ci) 中,其中 ri 是棋盘行号(从上到下从 1 到 n 编号),ci 是棋盘列号(从左到右从 1 到 n 编号)。没有两个女王拥有相同的位置。

对于每个皇后,可以计算 w — 给定皇后威胁(攻击)的其他皇后的数量。对于固定攻击方向,如果攻击射线上有许多皇后,则只有该方向上的第一个皇后受到攻击。显然,对于任何皇后,w 都在 0 到 8 之间(包含 0 和 8)。

打印序列 t0, t1, ..., t8,其中 ti 是恰好威胁 i 个其他皇后的皇后数量,即 w 等于 i 的皇后数量。

输入

输入的第一行包含一对整数 n, m (1 ≤ n, m ≤ 105),其中 n 是棋盘的大小,m 是棋盘上皇后的数量。然后接下来的 m 行包含皇后的位置,每行一个。每行包含一对整数 ri, ci (1 ≤ ri, ci ≤ n) — 皇后的位置。没有两个皇后站在同一个方格上。

输出

打印所需的序列 t0, t1, ..., t8,用空格分隔数字。

示例

输入 #1

8 4
4 3
4 8
6 5
1 6

输出 #1

0 3 0 1 0 0 0 0 0

输入 #2

10 3
1 1
1 2
1 3

输出 #2

0 2 1 0 0 0 0 0 0