Зіткнення ферзів

Студенти комп'ютерних наук часто проводять багато часу, розташовуючи ферзів на шахівниці. Два ферзі на шахівниці атакують одне одного (відбувається зіткнення), якщо вони знаходяться на одній горизонталі, вертикалі чи діагоналі та між ними немає іншої фігури. Розглядаються дошки різних розмірів та різна кількість ферзів. Наприклад, на рисунку 1 дошка 7\times 7 містить $7$ ферзів, які не атакують одне одного. На рисунку 2 показана дошка 5\times 5 з $5$ ферзями і $4$ зіткненнями. На рисунку 3 традиційна дошка 8\times 8 містить $7$ ферзів і $5$ зіткнень.

На дошці розміром n\times n позиції ферзів задаються у декартових координатах $(x,y)$, де $x$ — номер стовпця від $1$ до $n$, а $y$ — номер рядка від $1$ до $n$. Ферзі на різних позиціях (x_1, y_1) та (x_2, y_2) знаходяться на одній діагоналі, якщо |x_1-x_2| = |y_1-y_2|. Вони знаходяться на одній горизонталі або вертикалі, якщо y_1 = y_2 або x_1 = x_2 відповідно. У кожному з цих випадків виникає зіткнення, якщо між ними у тому ж напрямку немає іншого ферзя. Наприклад, на рисунку 2 зіткнення є між ферзями у позиціях $(5,1)$ та $(4,2)$, $(4,2)$ та $(3,3)$, $(3,3)$ та $(2,4)$, і нарешті $(2,4)$ та $(1,5)$. На рисунку 3 зіткнення між ферзями у позиціях $(1,8)$ та $(4,8)$, $(4,8)$ та $(4,7)$, $(4,7)$ та $(6,5)$, $(7,6)$ та $(6,5)$ і, нарешті, $(6,5)$ та $(2,1)$. Ваше завдання — підрахувати кількість зіткнень між ферзями.

У багатьох випадках ферзі розміщені у певному закономірному порядку. Наприклад, на рисунку 1 є $4$ ферзі підряд у точках $(1,1)$, $(2,3)$, $(3,5)$ та $(4,7)$. Кожен наступний ферзь після першого у $(1,1)$ стоїть на одну клітинку правіше і на дві вище попереднього. Три ферзі, починаючи з $(5,2)$, розміщені за подібною схемою. Виявлення таких закономірностей дозволяє стисло описувати розташування великої кількості ферзів.

7 2
4 1 1 1 2
3 5 2 1 2
5 1
5 1 1 1 1
8 4
1 1 8 0 0
2 4 8 0 -1
2 6 5 1 1
2 2 1 1 1
0

0
4
5