SP697 MWORDS - Matrix Words

给定一个 $N \times N$ 的字符矩阵。我们从位置 $(1, 1)$ 开始，目标是在恰好 $2N-1$ 步内到达 $(N, N)$。每次可以向上下左右移动一步。在此过程中，我们收集所经过位置的字符，拼接形成一个字符串。我们要求所有路径，不得穿过矩阵的主对角线，但路径可以部分通过对角线。这些路径分为两类：对角线上方和对角线下方的路径。每条路径将由沿途收集的字符依次组成一个字符串。如果将所有的合法路径（包括上方和下方）生成的字符串按字母顺序排列，我们就得到一个"主集合"。注意，主集合中可能会有重复项，所有字符串长度均为 $2N-1$。假设主集合中共有 $M$ 个字符串，给定一个整数 $I$，我们需要找到主集合中索引为 $I \mod M$ 的字符串。 例如，假设主集合为 {“A”, “B”, “B”, “C”}（尽管这种情况不可能真正出现），当 $I=0$ 时，对应的字符串是“A”；而 $I=2$ 和 $I=5$ 时，对应的字符串是“B”。 **约束条件：** - $N \leq 30$。 - $I \leq 10^{18}$。$I$ 是一个可用 64 位整数表示的数。

- 第一行是一个整数 $T$，表示有多少组测试数据。 - 对于每组测试数据，第一行包含两个整数 $N$ 和 $I$。 - 接下来是一个 $N \times N$ 的字符矩阵，每行包含 $N$ 个字符。 - 字符全部为大写字母，从 'A' 到 'Z' 。

对于每组测试数据，输出在主集合中对应的字符串。 **本翻译由 AI 自动生成**