Queen Collisions

Several queens are placed on a chessboard. Two distinct queens collide if they lie on the same row, the same column, or the same diagonal, and there is no other queen between them along that line. The board size and the number of queens vary from case to case.

On an $n \times n$ board, each queen's position is written as coordinates $(x, y)$, where $x$ is a column number from $1$ to $n$ and $y$ is a row number from $1$ to $n$. Two distinct positions $(x_1, y_1)$ and $(x_2, y_2)$ are related as follows:

• If $y_1 = y_2$, they lie on the same row.
• If $x_1 = x_2$, they lie on the same column.
• If $|x_1 - x_2| = |y_1 - y_2|$, they lie on the same diagonal.

In each of these cases the two queens collide only if no other queen lies directly between them along that line (row, column, or diagonal). Hence, when several queens lie on one line, only the neighboring queens along that line collide. For example, if the five queens $(5, 1), (4, 2), (3, 3), (2, 4), (1, 5)$ lie on one anti-diagonal, the collisions occur only between the four pairs $(5,1)$–$(4,2)$, $(4,2)$–$(3,3)$, $(3,3)$–$(2,4)$, and $(2,4)$–$(1,5)$.

Queens are often placed in regular patterns. Such regularity lets the positions of many queens be stated compactly, so the input is given as groups of queens placed in arithmetic progression (linear patterns). Write a program that counts the total number of collisions in the given arrangement.

The input consists of one to twenty data sets, followed by a line containing only $0$.

The first line of each data set contains two blank-separated positive integers $n$ and $g$. Here $n$ means the board size is $n \times n$ with $n < 30000$, and $g$ is the number of linear patterns described next with $g < 250$. Each of the next $g$ lines contains five blank-separated integers $k\ x\ y\ s\ t$, representing $k$ queens placed at positions $(x + i \cdot s,\ y + i \cdot t)$ for $i = 0, 1, \dots, k-1$. The value $k$ is a positive integer. If $k = 1$, the values of $s$ and $t$ are irrelevant and are given as $0$.

Every queen position lies on the board. The total number of queen positions across all linear patterns in one data set does not exceed $n$, and all of these positions are distinct.

For each data set, print on one line the total number of collisions in that arrangement.

The number of queens can be large, so take care that your algorithm is efficient.