Alice 和 Bob 在长度为 $$$n$$$ 的二进制字符串 $$$s$$$(仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串)上玩游戏。爱丽丝先行动,玩家轮流行动。
在一个回合中,玩家选择一系列索引 $$$i_1, i_2, \ldots, i_m$$$ ($$$1 \le i_1 \lt i_2 \lt \ldots \lt i_m \le n$$$),使得这些位置的字符形成一个 非增加 序列(即 $$$s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_m}$$$)。然后玩家重新排列这些位置上的角色以进行排序 非递减 订单。
正式地,让所选字符由 $$$z$$$ 零和 $$$o$$$ 组成(其中 $$$z + o = m$$$)。该移动将位置 $$$i_1、i_2、\ldots、i_m$$$ 处的字符替换为一系列 $$$z$$$ 零,后跟 $$$o$$$ 1。当且仅当严格执行时,移动才是有效的 修改 字符串 $$$s$$$ (这意味着 $$$z \ge 1$$$ 和 $$$o \ge 1$$$)。
无法做出有效动作的玩家失败。
假设两名玩家都发挥最佳,确定获胜者。如果爱丽丝获胜,则输出有效的第一步,这是获胜策略的一部分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行由一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 组成 - 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一到三行:
- 如果 Bob 以最佳发挥获胜,则打印一行包含“鲍勃".
- 否则,打印三行。在第一行打印“爱丽丝"。在第二行打印一个整数 $$$m$$$ ($$$2 \le m \le n$$$),在第三行打印 $$$m$$$ 不同的整数 $$$i_1, i_2, \ldots, i_m$$$ ($$$1 \le i_1 \lt i_2 \lt \ldots \lt i_m \le n$$$) —为爱丽丝的第一步选择的指数。
您打印的索引序列必须根据语句中描述的规则形成有效的移动。索引必须打印在 递增顺序。如果有多个获胜动作,您可以输出其中任何一个。
示例
输入复制
330002103101
输出复制
BobAlice21 2Alice21 2
注意
在第一个例子中,没有办法在 $$$s$$$ 发生变化后采取行动,所以 Bob 立即获胜。
在第三个例子中,Alice 可以选择一个子序列 $$$[1, 2]$$$ 并对其进行排序,之后 $$$s$$$ 将变成 $$$\mathtt{011}$$$。此后,鲍勃无法采取行动,因此爱丽丝获胜。