Status:  Past  Start:  20111201 14:00:00  End:  20111201 19:10:00 
The Caribbean Training Contest #29
Problem
1642  Yet Another Queens Problem
Created by  Yonny Mondelo Hernández 
Added by  ymondelo20 (20111129) 
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 ith 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 moveattack 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 ith queen threatens (attacks).
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 moveattack 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 ith queen threatens (attacks).
There are M queens on a square N x N chessboard. You know each queen's positions, the ith 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 moveattack 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 ith queen threatens (attacks).
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 moveattack 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 ith queen threatens (attacks).
There are M queens on a square N x N chessboard. You know each queen's positions, the ith 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 moveattack 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 ith queen threatens (attacks).
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 moveattack 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 ith 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 ith 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 ith 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 ith 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 ith 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/