E. Еще одна задача о ферзях
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Ферзь (перс. 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