1642 - Yet Another Queens Problem

Created by Yonny Mondelo Hernández
Added by ymondelo20 (2011-11-29)
Limits
Total Time: 25000 MS | Test Time: 2500 MS |Memory: 62 MB | Output: 64 MB | Size: 14 KB
Enabled languages
Available in

Description

There are M queens on a square N x N chessboard. You know each queen's positions, the i-th queen is positioned in the square (ri, ci), where ri is the board row number (numbered from the top to the bottom from 1 to N), and ci 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 we can count W - the number of other queens that the given queen threatens (attacks). A queen is the strongest chess piece. In modern chess the queen can move-attack 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. Obviously, for any queen W is between 0 and 8, inclusive.

You must calculate and print a sequence W1, W2, ..., WM, where Wi is the number of other queens that the i-th queen threatens (attacks).
There are M queens on a square N x N chessboard. You know each queen's positions, the i-th queen is positioned in the square (ri, ci), where ri is the board row number (numbered from the top to the bottom from 1 to N), and ci 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 we can count W - the number of other queens that the given queen threatens (attacks). A queen is the strongest chess piece. In modern chess the queen can move-attack 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. Obviously, for any queen W is between 0 and 8, inclusive.

You must calculate and print a sequence W1, W2, ..., WM, where Wi is the number of other queens that the i-th queen threatens (attacks).
There are M queens on a square N x N chessboard. You know each queen's positions, the i-th queen is positioned in the square (ri, ci), where ri is the board row number (numbered from the top to the bottom from 1 to N), and ci 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 we can count W - the number of other queens that the given queen threatens (attacks). A queen is the strongest chess piece. In modern chess the queen can move-attack 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. Obviously, for any queen W is between 0 and 8, inclusive.

You must calculate and print a sequence W1, W2, ..., WM, where Wi is the number of other queens that the i-th queen threatens (attacks).

Input specification

The first line of the input contains a pair of integers N, M (1 <= N,M <= 10^5; M <= N^2), 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 ri, ci (1 <= ri, ci <= N) - the i-th queen's position.
The first line of the input contains a pair of integers N, M (1 <= N,M <= 10^5; M <= N^2), 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 ri, ci (1 <= ri, ci <= N) - the i-th queen's position.
The first line of the input contains a pair of integers N, M (1 <= N,M <= 10^5; M <= N^2), 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 ri, ci (1 <= ri, ci <= N) - the i-th queen's position.

Output specification

Print the required sequence W1, W2, ..., WM, separating the numbers with spaces.

Print the required sequence W1, W2, ..., WM, separating the numbers with spaces.

The first line of the input contains a pair of integers N, M (1 <= N,M <= 10^5; M <= N^2), 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 ri, ci (1 <= ri, ci <= N) - the i-th queen's position.

Sample input

8 4
4 3
4 8
6 5
1 6

Sample output

3 1 1 1

Hint(s)

http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/