题目描述

有一个由 31 个格子组成的六边形数独棋盘，格子编号为 $1\sim31$。你需要在每个格子中填入一个 $1\sim K$ 的整数。

棋盘示意如下，其中带 * 的格子为特殊标记格：

                 1     2
           3     4     5*    6     7
        8     9*   10    11    12*   13
          14    15    16*   17    18
       19    20*   21    22    23*   24
          25    26    27*   28    29
                30    31

需要满足下面两类限制。

1. 三个方向上的每一行数字互不相同

水平方向的 7 行：

1 2
3 4 5 6 7
8 9 10 11 12 13
14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29
30 31

/ 方向的 7 行：

3 8
1 4 9 14 19
2 5 10 15 20 25
6 11 16 21 26
7 12 17 22 27 30
13 18 23 28 31
24 29

\ 方向的 7 行：

7 13
2 6 12 18 24
1 5 11 17 23 29
4 10 16 22 28
3 9 15 21 27 31
8 14 20 26 30
19 25

同一行中的所有数字必须两两不同。

2. 特殊标记格及其相邻格数字互不相同

共有 7 个特殊标记格：$5,9,12,16,20,23,27$。对每个标记格，它自身以及周围 6 个相邻格构成一个 7 格区域，其中的数字必须两两不同：

5  : 1 2 4 5 6 10 11
9  : 3 4 8 9 10 14 15
12 : 6 7 11 12 13 17 18
16 : 10 11 15 16 17 21 22
20 : 14 15 19 20 21 25 26
23 : 17 18 22 23 24 28 29
27 : 21 22 26 27 28 30 31

输入中可能已经有一些格子填好了数字，这些预填数字本身满足上述规则。

把一个完整解记为 $A_1,A_2,\dots,A_{31}$。所有合法完整解按字典序排列：若存在位置 $j$，使得对所有 $i<j$ 都有 $A_i=B_i$，并且 $A_j<B_j$，则称解 $A$ 的字典序小于解 $B$。

你的任务是求字典序第 $N$ 个合法完整解。如果合法解不足 $N$ 个，则输出无解。

输入格式

第一行包含两个整数 $K,N$。

• $7\le K\le31$；
• $1\le N\le100000$。

第二行包含 31 个整数 $A_1,A_2,\dots,A_{31}$：

• $A_i=0$ 表示第 $i$ 个格子尚未填写；
• 否则 $1\le A_i\le K$，表示该格已经预填为 $A_i$。

保证所有预填数字按照题目规则放置。

输出格式

如果不存在第 $N$ 个合法解，输出：

No way

否则第一行输出：

Found

第二行输出 31 个整数，表示字典序第 $N$ 个合法完整解。

样例 1

8 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Found
1 2 1 3 4 5 2 2 4 6 7 1 3 7 5 1 8 6 2 1 3 4 5 7 8 6 7 2 3 5 8

样例 2

7 100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

No way

难度评定

约 Codeforces 2600。

核心是把 28 组“互不相同”约束建成固定冲突图，然后按格子编号从小到大、颜色从小到大 DFS，从而天然按字典序枚举完整解。为了在 $N\le100000$ 时稳定通过，需要使用候选颜色位集、冲突计数和前向检查来快速剪枝。

时间与空间限制

• 时间限制：4 秒
• 空间限制：256 MB