Зіткнення королев
Багато часу студенти комп'ютерних наук витрачають на розв'язання задач з ферзями на шаховій дошці. Два ферзі на шаховій дошці стикаються, якщо вони знаходяться на одному рядку, стовпці або діагоналі, і між ними немає інших фігур. Розглядаються дошки різних розмірів і кількість ферзів. Наприклад, на Рисунку 1, на дошці 7x7, розміщено 7 ферзів без зіткнень. На Рисунку 2 є дошка 5x5 з 5 ферзями і 4 зіткненнями. На Рисунку 3, традиційна дошка 8x8, містить 7 ферзів і 5 зіткнень.
На дошці nxn позиції ферзів задаються в декартових координатах (x, y), де x - номер стовпця, від 1 до n, а y - номер рядка, від 1 до n. Ферзі в різних позиціях (x_1, y_1) і (x_2, y_2) знаходяться на одній діагоналі, якщо (x_1- x_2) і (y_1- y_2) мають однакову величину. Вони знаходяться на одному рядку або стовпці, якщо x_1= x_2 або y_1= y_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) знаходиться на одну вправо і 2 вгору від попереднього. Три ферзі, починаючи з (5, 2), слідують подібному шаблону. Відзначення цих шаблонів дозволяє стисло вказати позиції великої кількості ферзів.
Вхідні дані
Вхідні дані складатимуться з одного до двадцяти наборів даних, за якими слідує рядок, що містить лише 0.
Перший рядок набору даних містить розділені пробілами додатні цілі числа n g, де n вказує розмір дошки n x n, а g - кількість лінійних шаблонів ферзів, які потрібно описати, де n < 30000, і g < 250. Наступні g рядків кожен містить п'ять розділених пробілами цілих чисел, k x y s t, що представляють лінійний шаблон з k ферзів на позиціях (x + i*s, y +i*t), для i = 0, 1, ..., k-1. Значення k є додатним. Якщо k дорівнює 1, то значення s і t не мають значення, і вони будуть задані як 0. Усі позиції ферзів будуть на дошці. Загальна кількість позицій ферзів серед усіх лінійних шаблонів не перевищуватиме n, і всі ці позиції ферзів будуть різними.
Вихідні дані
Для кожного набору даних виведіть один рядок, що містить лише кількість зіткнень між ферзями.
Набір вхідних даних відповідає конфігурації на рисунках.
Будьте уважні з вашим алгоритмом, інакше ваше рішення може зайняти занадто багато часу.