你在一家公司工作，该公司有 $E$ 名员工在城镇 $T$ 工作。员工居住的地区共有 $N$ 个城镇。你想确保每个人都能去上班。部分员工是司机，可以搭载 $P$ 名乘客。容量 $P = 1$ 表示司机只能载自己去上班。你想确保每个人都能去上班，并且希望最小化路上的汽车数量。

你需要计算路上的汽车数量，并满足以下要求：

• 每个员工都能到达城镇 $T$。
• 员工在城镇之间出行的唯一方式是乘坐属于员工的汽车。
• 员工只能搭乘与自己住在同一城镇的其他员工的车。
• 使用最少数量的汽车。

判断是否可能让每个人都成功去上班，如果可以，最终会有多少辆车开往办公室。

输入格式

第一行包含一个整数 $C$，表示输入文件中的测试用例数量。

每个测试用例包括：

• 一行包含整数 $N$（你所在区域的城镇数量）和整数 $T$（办公室所在的城镇）。
• 一行包含整数 $E$（员工数量）。
• $E$ 行，每行对应一名员工，包含：
  • 一个整数 $H \ge 1$，表示该员工居住的城镇，后跟
  • 一个整数 $P \ge 0$，表示他们可以搭载的乘客数量。如果该员工没有驾照，则该数字为 $0$。

输出格式

输出 $C$ 行，每个测试用例对应一行，按输入文件中的顺序排列。每行包含字符串 Case #X:，其中 $X$ 是测试用例的编号（从 $1$ 开始），后跟：

• 字符串 IMPOSSIBLE（如果司机不足以让所有人通勤）；或者
• $N$ 个空格分隔的整数，分别对应从城镇 $1$ 到 $N$，表示从该城镇通勤的车辆数量。

数据范围

• $1 \le T \le N$
• $1 \le H \le N$
• $0 \le P \le 6$

小数据规模（9 分）

• $C = 50$
• $1 \le N \le 10$
• $1 \le E \le 100$

大数据规模（9 分）

• $C = 100$
• $1 \le N \le 100$
• $1 \le E \le 500$

样例

输入样例 1

3
5 1
3
1 0
1 0
1 0
5 1
3
2 4
2 0
3 0
5 3
5
1 2
1 0
4 2
4 4
4 0

输出样例 1

Case #1: 0 0 0 0 0
Case #2: IMPOSSIBLE
Case #3: 1 0 0 1 0