Ферзь (перс. ferzin — визирь, советник) — самая сильная шахматная фигура. В современных шахматах ферзь может перемещаться на любое число полей по вертикали, горизонтали и диагонали, объединяя возможности ладьи и слона (при условии, что на его пути нет фигур).
На шахматной доске размера n × n стоят m ферзей. Известны позиции каждого из ферзей, i-й ферзь находится в клетке (ri, ci), где ri — номер строки доски (пронумерованы сверху вниз от 1 до n), а ci — номер столбца доски (пронумерованы слева направо от 1 до n). Позиции никакой пары ферзей не совпадают.
Для каждого ферзя можно посчитать количество других ферзей, которые находятся под его боем. Для фиксированного направления ферзь держит под боем лишь первую фигуру в этом направлении на его пути от его положения. Очевидно, что для каждого ферзя это число может быть любым от 0 до 8, включительно.
Выведите последовательность t0, t1, ..., t8, где ti — количество ферзей, которые держат под боем ровно i других ферзей.
Выходные данные
Выведите искомую последовательность t0, t1, ..., t8, разделяя числа пробелами.