31451번 - Five in a Row 다국어

Five in a Row, also called Gomoku, is a board game played with Go pieces (black and white stones). The winner is the first player to form an unbroken line of five stones of their color horizontally, vertically, or diagonally.

During leisure time at the Olympics, athletes and coaches also enjoy playing this game for recreation. Nevertheless, today they are playing a more advanced version in a $K$-dimensional board instead of a traditional $2$-dimensional board. Stones A, B, C, D, E are considered as five in a row if, for every integer $i$ such that $1 \le i \le K$, we have:

$A[i] - B[i] = B[i] - C[i] = C[i] - D[i] = D[i] - E[i] =$ one of $\{-1, 0, 1\}$.

Here, $A[i]$ is the coordinate of the stone $A$ on the $i$^th dimension.

Due to the complexity of the board, they sometimes get overwhelmed. Therefore you are asked to write a referee program that takes all the moves made by one player in chronological order and calculates after placing which stone we see five in a row for the first time.

The first line contains two space-separated integers $K$ and $N$: $K$ is the number of dimensions of the board, and $N$ is the number of stones. This line is followed by $N$ lines, which describe the $N$ stones placed by one player in chronological order. The $i$^th such line contains $K$ space-separated integers $x_1, x_2, \dots , x_K$, which are the $K$ coordinates of the $i$^th stone.

The output should contain a single line. This line must contain the smallest positive integer $i$ for which we see five in a row after placing the $i$^th stone; or NOT ALIGNED if such an integer $i$ does not exist.

• $1 \le K \le 15$
• $5 \le N \le 2\, 000$
• the $N$ stones have been placed in distinct positions on the board
• each coordinate $x_i$ is an integer such that $-10\, 000 \le x_i \le 10\, 000$