Queen Collisions
Студенты, изучающие информатику, потратили много времени на исследование расположения ферзей на шахматной доске. Два ферзя считаются сталкивающимися, если они находятся на одной и той же строке, столбце или диагонали, и между ними нет других фигур. Мы рассматриваем доски различных размеров и количество ферзей. Например, на Рисунке 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, и все эти позиции ферзей будут различными.
Выходные данные
Для каждого набора данных выводится одна строка, содержащая только количество столкновений между ферзями.
Пример входных данных соответствует конфигурации на рисунках.
Будьте внимательны с вашим алгоритмом, иначе ваше решение может занять слишком много времени.