Description

参议院会议厅里起了一场小火，必须进行疏散！

会议厅里有若干参议员，每位参议员都属于 $\mathbf{N}$ 个政党中的某一个。这些政党的名称分别为英语字母表前 $\mathbf{N}$ 个大写字母。

紧急出口足够宽敞，每一步疏散时你可以选择移除一名或两名参议员。

参议院的规则规定，即使在疏散过程中，会议厅里的参议员也可以随时对任何议案进行投票！因此，疏散必须以一种方式进行，保证任何时刻都不会有某个政党拥有绝对多数。也就是说，在任何一次疏散操作之后，会议厅中都不能出现某个政党成员人数超过总人数一半的情况。

你能制定一个疏散方案吗？参议院全靠你了！

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例包含两行。第一行是一个整数 $\mathbf{N}$，表示政党数量。第二行包含 $\mathbf{N}$ 个整数，$\mathbf{P}_1, \mathbf{P}_2, \ldots, \mathbf{P}_\mathbf{N}$，其中 $\mathbf{P}_i$ 表示以字母表第 $i$ 个字母命名的政党拥有的参议员人数。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 是疏散方案。方案应为一个以空格分隔的操作序列，每个操作为一个或两个字母，表示本次疏散中被移除的参议员所属政党。

保证至少存在一种合法的疏散方案。如果有多种方案，你可以输出任意一种。

4
2
2 2
3
3 2 2
3
1 1 2
3
2 3 1

Case #1: AB BA
Case #2: AA BC C BA
Case #3: C C AB
Case #4: BA BB CA

Hint

样例解释

样例输出展示的是一组可能的答案，其他答案也可能是正确的。

在第 1 组中，A 和 B 两个政党各有两名参议员。如果每次各移除一人，始终保持完美平衡，直到全部疏散。

第 2 组操作如下：

• 初始：3 名 A，2 名 B，2 名 C。
• 疏散 AA。剩余：1 名 A，2 名 B，2 名 C。
• 疏散 BC。剩余：1 名 A，1 名 B，1 名 C。
• 疏散 C。剩余：1 名 A，1 名 B。
• 疏散 AB。全部疏散完成！

注意，不能以 BC 开始疏散，否则剩下 3 名 A，1 名 B，1 名 C，A 党将拥有绝对多数（3/5 = 60%）。

对于第 3 组，CC AB 也是一个合法答案，C C AB 也是合法的，尽管需要三步而不是两步。

限制条件

• $1 \leqslant \mathbf{T} \leqslant 50$。
• 在疏散开始前，没有任何政党拥有绝对多数。
• 对所有 $i$，$1 \leqslant \mathbf{P}_i \leqslant 1000$。

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

• $2 \leqslant \mathbf{N} \leqslant 3$。
• 所有 $\mathbf{P}_i$ 之和 $\leqslant 9$。

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

• $2 \leqslant \mathbf{N} \leqslant 26$。
• 所有 $\mathbf{P}_i$ 之和 $\leqslant 1000$。

翻译由 GPT4.1 完成。