小藍(lán)最近迷上了一款名為《數(shù)字接龍》的迷宮游戲，游戲在一個(gè)大小為N × N 的格子棋盤上展開，其中每一個(gè)格子處都有著一個(gè) 0 . . . K ? 1 之間的整數(shù)。游戲規(guī)則如下：

1. 從左上角 (0, 0) 處出發(fā)，目標(biāo)是到達(dá)右下角 (N ? 1, N ? 1) 處的格子，每一步可以選擇沿著水平/垂直/對(duì)角線方向移動(dòng)到下一個(gè)格子。

2. 對(duì)于路徑經(jīng)過(guò)的棋盤格子，按照經(jīng)過(guò)的格子順序，上面的數(shù)字組成的序列要滿足：0, 1, 2, . . . , K ? 1, 0, 1, 2, . . . , K ? 1, 0, 1, 2 . . . 。

3. 途中需要對(duì)棋盤上的每個(gè)格子恰好都經(jīng)過(guò)一次（僅一次）。

4. 路徑中不可以出現(xiàn)交叉的線路。例如之前有從 (0, 0) 移動(dòng)到 (1, 1)，那么再?gòu)?(1, 0) 移動(dòng)到 (0, 1) 線路就會(huì)交叉。

為了方便表示，我們對(duì)可以行進(jìn)的所有八個(gè)方向進(jìn)行了數(shù)字編號(hào)，如下圖2 所示；因此行進(jìn)路徑可以用一個(gè)包含 0 . . . 7 之間的數(shù)字字符串表示，如下圖 1是一個(gè)迷宮示例，它所對(duì)應(yīng)的答案就是：41255214。

現(xiàn)在請(qǐng)你幫小藍(lán)規(guī)劃出一條行進(jìn)路徑并將其輸出。如果有多條路徑，輸出字典序最小的那一個(gè)；如果不存在任何一條路徑，則輸出 ?1。

3 3
0 2 0
1 1 1
2 0 2

41255214