Codeforces Beta Round 95 (Div. 2) |
---|
Закончено |
Ферзь (перс. ferzin — визирь, советник) — самая сильная шахматная фигура. В современных шахматах ферзь может перемещаться на любое число полей по вертикали, горизонтали и диагонали, объединяя возможности ладьи и слона (при условии, что на его пути нет фигур).
На шахматной доске размера n × n стоят m ферзей. Известны позиции каждого из ферзей, i-й ферзь находится в клетке (ri, ci), где ri — номер строки доски (пронумерованы сверху вниз от 1 до n), а ci — номер столбца доски (пронумерованы слева направо от 1 до n). Позиции никакой пары ферзей не совпадают.
Для каждого ферзя можно посчитать количество других ферзей, которые находятся под его боем. Для фиксированного направления ферзь держит под боем лишь первую фигуру в этом направлении на его пути от его положения. Очевидно, что для каждого ферзя это число может быть любым от 0 до 8, включительно.
Выведите последовательность t0, t1, ..., t8, где ti — количество ферзей, которые держат под боем ровно i других ферзей.
В первой строке входных данных записана пара целых чисел n, m (1 ≤ n, m ≤ 105), где n — размер доски, а m — количество ферзей на доске. Далее в m строках записаны позиции ферзей, по одной позиции в строке. Каждая строка содержит пару целых чисел ri, ci (1 ≤ ri, ci ≤ n) — позицию ферзя. Никакие два ферзя не находятся в одной клетке.
Выведите искомую последовательность t0, t1, ..., t8, разделяя числа пробелами.
8 4
4 3
4 8
6 5
1 6
0 3 0 1 0 0 0 0 0
10 3
1 1
1 2
1 3
0 2 1 0 0 0 0 0 0
Название |
---|