Yet Another Task with Queens

题意翻译

皇后是最强的棋子。在现代国际象棋中，皇后可以在任何水平、垂直或对角线方向上移动任意数量的方格（考虑到在其途中没有其他棋子）。女王结合了车和主教的技能。 $n\times n$方格棋盘上有 $m$ 个皇后 ，你知道每个女王的位置是 $(r_i,c_i)$ ，$r_i$ 是行，$c_i$ 是列。没有两个皇后处于同一位置。 对于每一个女王，我们可以计算 $w$ ——该女王威胁（攻击）的其他女王的数量。对于固定的攻击方向，如果有许多皇后处于攻击射线上，则只有该方向上的第一个皇后受到攻击。显然，对于任何女王来说，$0<=w<=8$ 。 打印序列 $t_0,t_1,...，t_8$，其中$t_i$是威胁其他皇后的皇后数量，即他们的 $w$ 等于 $i$ 的皇后数量。 ### 输入格式 第一行包含一对整数 $n,m$, $(1<=n,m<=10^{5})$ ，$n$ 是棋盘尺寸， $m$ 是棋盘上皇后数量。 接下来的几行包含皇后的位置，每行一对整数 $r_i,c_i$ 。 $(1<=r_i,c_i<=n)$ ，表示皇后的位置，且没有两个皇后处于同一位置。 ### 输出格式 打印序列 $t_0,t_1,...，t_8$ ,用空格分隔数字。

题目描述

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 $ .

输入输出格式

输入格式

The first line of the input contains a pair of integers $ n,m $ ( $ 1<=n,m<=10^{5} $ ), 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.

输出格式

Print the required sequence $ t_{0},t_{1},...,t_{8} $ , separating the numbers with spaces.

输入输出样例

输入样例 #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