Ферзь (перс. ferzin — визирь, советник) — самая сильная шахматная фигура. В современных шахматах ферзь может перемещаться на любое число полей по вертикали, горизонтали и диагонали, объединяя возможности ладьи и слона (при условии, что на его пути нет фигур).

На шахматной доске размера n × n стоят m ферзей. Известны позиции каждого из ферзей, i-й ферзь находится в клетке (r_i, c_i), где r_i — номер строки доски (пронумерованы сверху вниз от 1 до n), а c_i — номер столбца доски (пронумерованы слева направо от 1 до n). Позиции никакой пары ферзей не совпадают.

Для каждого ферзя можно посчитать количество других ферзей, которые находятся под его боем. Для фиксированного направления ферзь держит под боем лишь первую фигуру в этом направлении на его пути от его положения. Очевидно, что для каждого ферзя это число может быть любым от 0 до 8, включительно.

Выведите последовательность t₀, t₁, ..., t₈, где t_i — количество ферзей, которые держат под боем ровно i других ферзей.