题目描述

Alan 和 Barbara 突然想玩数字游戏。Alan 从前 $N$ 个正整数 $\{1,2,\ldots,N\}$ 中选出一个非空子集。Barbara 拿走剩下的数（如果有）。然后他们分别计算自己集合中元素的和。

Alan 相信一个神奇的比例 $X : Y$。因此，Alan 希望选择子集，使得 Alan 子集的和与 Barbara 子集的和之比恰好为 $X : Y$。

你能帮助 Alan 选出满足所需比例的子集吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例一行，包含三个整数 $N$、$X$ 和 $Y$，如上所述。

输出格式

对于每个测试用例，输出第一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 POSSIBLE（如果 Alan 能选出这样的非空子集），否则为 IMPOSSIBLE。

如果输出 POSSIBLE，则还需为该测试用例输出两行：

第二行输出一个整数，表示 Alan 子集的大小。

第三行输出 Alan 子集中的整数（顺序不限）。

如果有多个解，输出任意一个均可。

3
3 1 2
3 1 1
3 1 3

Case #1: POSSIBLE
1
2
Case #2: POSSIBLE
2
1 2
Case #3: IMPOSSIBLE

提示

在第一个测试用例中，Alan 选择 $\{2\}$，则 Barbara 得到 $\{1,3\}$，其和为 $1+3=4$，因此比例为 $2:4$，等价于 $1:2$。

在第二个测试用例中，Alan 选择 $\{1,2\}$，其和为 $1+2=3$，Barbara 得到 $\{3\}$，比例为 $3:3$，等价于 $1:1$。

在第三个测试用例中，Alan 无法选出满足条件的子集。

限制条件

$1 \le T \le 100$。

$1 \le X \le 10^8$。

$1 \le Y \le 10^8$。

$\gcd(X,Y)=1$，其中 gcd 表示最大公约数。

测试集 1

$1 \le N \le 15$。

测试集 2

$1 \le N \le 5000$。

翻译由 DeepSeek V4 Pro 完成