Background

So far, no solution has been found (without special-casing) that can prune effectively and pass the testdata with $n = 10$, $k = 1$. Since this problem is suspected to be wrong, this problem does not provide judging or an editorial section.

Problem Description

Xiao Lan recently became addicted to a maze game called "Number Snake". The game is played on an $n \times n$ grid board, where each cell contains an integer between $0 \cdots k-1$. The rules are as follows.

1. Start from the top-left cell $(0,0)$, and the goal is to reach the bottom-right cell $(n-1,n-1)$. At each step, you may move to the next cell in a horizontal / vertical / diagonal direction.
2. For the cells visited along the path, in the visiting order, the sequence formed by the numbers on them must be: $0,1,2, \cdots ,k-1,0,1,2, \cdots ,k-1,0,1,2 \cdots$.
3. Along the way, you must visit every cell on the board exactly once (only once).
4. The path must not contain crossing segments. For example, if you have moved from $(0,0)$ to $(1,1)$ before, then moving from $(1,0)$ to $(0,1)$ would make the segments cross, which is not allowed.

For convenience, we label all eight possible moving directions with numbers, as shown in Figure $2$. Therefore, a moving path can be represented by a digit string containing numbers between $0 \cdots 7$. As shown in Figure $1$, for a sample maze, the corresponding answer is: $41255214$.

Now please help Xiao Lan plan a moving path and output it. If there are multiple paths, output the lexicographically smallest one. If there is no such path, output $−1$.

Input Format

The first line contains two integers $n, k$. Then follow $n$ lines, each containing $n$ integers, representing the numbers on the grid cells.

Output Format

Output one line containing the answer. If there is no valid path, output $-1$.

3 3
0 2 0
1 1 1
2 0 2

41255214

Hint

Constraints

• For $80\%$ of the testdata, $n \leq 5$.
• For all testdata, $1 \leq n,k \leq 10$.

Translated by ChatGPT 5