퀸 충돌

체스판 위에 여러 개의 퀸이 놓여 있다. 서로 다른 두 퀸이 같은 행, 같은 열, 또는 같은 대각선 위에 있고, 그 사이(같은 직선 위)에 다른 퀸이 하나도 없으면 두 퀸은 충돌한다. 판의 크기와 퀸의 개수는 경우마다 다르게 주어진다.

$n \times n$ 판에서 각 퀸의 위치는 좌표 $(x, y)$로 나타낸다. $x$는 열 번호로 $1$부터 $n$까지, $y$는 행 번호로 $1$부터 $n$까지이다. 서로 다른 두 위치 $(x_1, y_1)$과 $(x_2, y_2)$는 다음과 같이 판정한다.

• $y_1 = y_2$이면 같은 행 위에 있다.
• $x_1 = x_2$이면 같은 열 위에 있다.
• $|x_1 - x_2| = |y_1 - y_2|$이면 같은 대각선 위에 있다.

이 세 경우 각각에 대해, 해당 직선(행·열·대각선)을 따라 두 퀸 사이에 다른 퀸이 하나도 없을 때에만 두 퀸은 충돌한다. 따라서 한 직선 위에 퀸이 여러 개 놓여 있으면, 그 직선을 따라 정렬했을 때 바로 이웃한 퀸끼리만 충돌한다. 예를 들어 어떤 반대각선 위에 다섯 퀸 $(5, 1), (4, 2), (3, 3), (2, 4), (1, 5)$가 놓이면, 충돌은 $(5,1)$–$(4,2)$, $(4,2)$–$(3,3)$, $(3,3)$–$(2,4)$, $(2,4)$–$(1,5)$의 네 쌍에서만 일어난다.

퀸들은 흔히 규칙적인 형태로 놓인다. 이런 규칙을 이용하면 많은 퀸의 위치를 간결하게 나타낼 수 있으므로, 입력은 등차적으로 배치된 퀸들의 묶음(선형 패턴)들로 주어진다. 주어진 배치에서 발생하는 충돌의 총 개수를 세는 프로그램을 작성하시오.

입력은 $1$개 이상 $20$개 이하의 데이터 집합으로 이루어지며, 마지막에는 $0$ 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 공백으로 구분된 두 양의 정수 $n$과 $g$가 주어진다. $n$은 판의 크기가 $n \times n$임을 뜻하며 $n < 30000$이고, $g$는 이어서 설명할 선형 패턴의 개수로 $g < 250$이다. 다음 $g$개의 줄에는 각각 공백으로 구분된 다섯 정수 $k\ x\ y\ s\ t$가 주어지며, 이는 위치 $(x + i \cdot s,\ y + i \cdot t)$ ($i = 0, 1, \dots, k-1$)에 놓인 $k$개의 퀸을 나타낸다. $k$는 양의 정수이다. $k = 1$이면 $s$와 $t$의 값은 의미가 없으며, 이때 두 값은 $0$으로 주어진다.

모든 퀸의 위치는 판 안에 있다. 한 데이터 집합의 모든 선형 패턴에 속한 퀸의 총 개수는 $n$을 넘지 않으며, 이 퀸들의 위치는 모두 서로 다르다.

각 데이터 집합마다 한 줄에 그 배치에서 발생하는 충돌의 총 개수를 출력한다.

퀸의 개수가 많을 수 있으므로 알고리즘의 효율에 주의해야 한다.