题目描述

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏。游戏在一个大小为 $N\times N$ 的格子棋盘上展开，其中每一个格子处都有着一个 $0\sim K-1$ 之间的整数。游戏规则如下：

1. 从左上角 $(0,0)$ 处出发，目标是到达右下角 $(N-1,N-1)$ 处的格子。每一步可以选择沿着水平、竖直、对角线方向移动到下一个格子。
2. 路径经过的棋盘格子，上面的数字需要按照 $0, 1, 2, ..., K-1, 0, 1, 2, ...$ 的顺序组成序列。
3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。
4. 路径中不可以出现交叉的线路。例如，之前如果从 $(0,0)$ 移动到 $(1,2)$ ，那么再从 $(1,0)$ 移动到 $(0,1)$ 就会形成交叉线路。

为了方便表示行进方向，对可以行进的八个方向进行了数字编号，如图 2 所示。因此，行进路径可以用一个包含 $0\sim 7$ 之间数字的字符串表示。

图 1 展示了一个迷宫示例，其对应的答案是：41255214。

输入格式

• 第一行包含两个整数 N 和 K。
• 接下来输入 N 行，每行 N 个整数，表示棋盘格子上的数字。

输出要求

• 输出一条满足条件的行进路径，路径用数字字符串表示。
• 如果有多条路径，输出字典序最小的那一个。
• 如果不存在任何一条路径，则输出-1。
• 如果不需要行进，则什么都不输出。

3 3
0 2 0
1 1 1
2 0 2

41255214

样例说明

行进路径如图 1 所示。

评测用例规模与约定

对于 80% 的评测用例： $1≤N≤5$。

对于 100% 的评测用例：$1≤N≤10,1≤K≤10$。

注意

本题目前未找到任何做法（在不进行特判的情况下）进行有效剪枝通过 n=10，k=1 的数据。

题目数据为随机生成。