Description

很久以前，Fractal 文明创造了一种由线性排列的瓷砖组成的艺术品。他们有两种类型的瓷砖可用：金砖（G）和铅砖（L）。

每件 Fractal 艺术品由两个参数决定：原始序列的长度 $\mathbf{K}$，以及复杂度 $\mathbf{C}$。对于一个给定的原始序列，复杂度为 $1$ 的艺术品就是原始序列本身，而复杂度为 $X+1$ 的艺术品则是将复杂度为 $X$ 的艺术品进行如下变换得到：

• 将复杂度 $X$ 艺术品中的每一个 $\mathbf{L}$ 替换为一份新的原始序列
• 将复杂度 $X$ 艺术品中的每一个 $\mathbf{G}$ 替换为 $K$ 个 $\mathbf{G}$

例如，若原始序列为 LGL，则复杂度 $1$ 到 $3$ 的艺术品分别为：

• $C = 1$：LGL（即原始序列本身）
• $C = 2$：LGLGGGLGL
• $C = 3$：LGLGGGLGLGGGGGGGGGLGLGGGLGL

下图展示了如何由复杂度 $1$ 的艺术品生成复杂度 $2$ 的艺术品：

你刚刚发现了一件 Fractal 艺术品，但瓷砖太脏了，无法分辨它们的材质。作为一名熟悉 Fractal 文化的考古专家，你知道这件艺术品的 $\mathbf{K}$ 和 $\mathbf{C}$，但不知道原始序列。由于金砖很珍贵，你想知道这件艺术品中是否至少有一块 $\mathbf{G}$。你的预算允许你雇佣 $\mathbf{S}$ 个研究生，每个人可以清理你指定的任意一块瓷砖（在总共 $\mathbf{K}^{\mathbf{C}}$ 块瓷砖中），以判断其材质是 $\mathbf{G}$ 还是 $\mathbf{L}$。

你能否选择不超过 $\mathbf{S}$ 块特定瓷砖进行清理，使得无论原始序列为何，你都能确定艺术品中是否至少存在一块 $\mathbf{G}$？如果可以，你应该清理哪些瓷砖？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数。接下来有 $\mathbf{T}$ 组测试用例，每组一行，包含三个整数：$\mathbf{K}, \mathbf{C}, \mathbf{S}$。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 若无论如何都无法确定答案，则为 $\mathbf{IMPOSSIBLE}$；否则为 $1$ 到 $\mathbf{S}$ 个正整数，表示需要清理的瓷砖编号（从左到右分别为 $1$ 到 $\mathbf{K}^{\mathbf{C}}$）。输出的编号顺序任意，但不得重复。

如有多种合法方案，你可以输出任意一种。

5
2 3 2
1 1 1
2 1 1
2 1 2
3 2 3

Case #1: 2
Case #2: 1
Case #3: IMPOSSIBLE
Case #4: 1 2
Case #5: 2 6

Hint

样例解释

注意：部分样例存在其他合法解。

在样例第 1 组中，原始序列可能为 GG、GL、LG、LL，分别生成如下艺术品：

• GG：GGGGGGGG
• GL：GGGGGGGL
• LG：LGGGGGGG
• LL：LLLLLLLL

一个可行方案是只查看第 2 块瓷砖。如果第 2 块为 G，你就能确定艺术品中至少有一块 G（虽然不能确定原始序列是哪一个，但这无关紧要）。如果第 2 块为 L，则原始序列必为 LL，艺术品中没有 G。因此，2 是一个合法方案。

另一方面，仅查看第 1 块是不合法的。如果它为 L，你无法区分原始序列是 LG 还是 LL。若为 LG，则艺术品中有 G；若为 LL，则没有。因此 1 不是合法方案。

注意 1 2 也是合法方案，因为第 2 块已经足够提供全部信息。1 2 3 就不合法，因为使用的瓷砖数超过了限制。

在样例第 2 组中，艺术品只有一块瓷砖：G 或 L。查看该瓷砖即可直接判断是否有 G。

在样例第 3 组（不会出现在小数据集），艺术品可能为 GG、GL、LG、LL。你只能查看一块瓷砖，任意一块都无法完全确定答案。例如查看第 1 块为 L 时，无法区分 LG 和 LL，也就无法判断是否有 G。

样例第 4 组与第 3 组类似，但你可以查看两块瓷砖。此时你可以直接查看全部艺术品。

在样例第 5 组中，原始序列有 8 种可能，生成如下艺术品：

• GGG：GGGGGGGGG
• GGL：GGGGGGGGL
• GLG：GGGGLGGGG
• GLL：GGGGLLGLL
• LGG：LGGGGGGGG
• LGL：LGLGGGLGL
• LLG：LLGLLGGGG
• LLL：LLLLLLLLL

一种可行方案是查看第 2 块和第 6 块。如果它们都是 L，则艺术品全为 L。否则至少有一块 G。注意 1 2 不是合法方案，因为若两块都是 L，原始序列可能为 LLG，此时艺术品中仍有 G。6 2 也是合法方案，顺序无关。

限制条件

• $1 \leq \mathbf{T} \leq 100$。
• $1 \leq \mathbf{K} \leq 100$。
• $1 \leq \mathbf{C} \leq 100$。
• $\mathbf{K}^{\mathbf{C}} \leq 10^{18}$。

小数据集（10 分，测试集 1 - 可见）

• $\mathbf{S} = \mathbf{K}$。

大数据集（25 分，测试集 2 - 隐藏）

• $1 \leq \mathbf{S} \leq \mathbf{K}$。

翻译由 GPT4.1 完成。