简单版本和困难版本之间的唯一区别是简单版本中给定的字符串 $$$s$$$ 最初是回文,这个条件对于困难版本并不总是成立。
回文是从左到右和从右到左读取相同的字符串。例如,“101101”是回文,而“0101”则不是。
Alice 和 Bob 正在玩一个游戏,字符串 $$$s$$$ 长度为 $$$n$$$,由字符“0”和“1”组成。两名玩家轮流玩,爱丽丝先玩。
在每一回合中,玩家可以执行以下操作之一:
1. 选择任意 $$$i$$$ ($$$1 \le i \le n$$$),其中 $$$s[i] =$$$ '0' 并将 $$$s[i]$$$ 更改为 '1'。支付1美元。
2. 反转整个字符串,支付 0 美元。仅当字符串当前不是回文且上次操作不是反向时才允许进行此操作。也就是说,如果 Alice 反转了字符串,那么 Bob 就无法在下一步中反转,反之亦然。
反转字符串意味着将其字母从最后一个字母重新排序到第一个字母。例如“01001”反转后就变成了“10010”。
当字符串的每个字符都变为“1”时游戏结束。到目前为止花费最少美元的玩家赢得游戏,如果双方花费相同的美元,则平局。如果两个玩家都发挥最佳,则输出 Alice 获胜、Bob 获胜还是平局。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^3$$$)。
每个测试用例的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字符“0”和“1”组成。保证字符串 $$$s$$$ 至少包含一个“0”。
请注意,测试用例中 $$$n$$$ 的总和没有限制。
输出
对于每个测试用例,在新行中打印一个单词:
- “ALICE”,如果爱丽丝赢得了比赛,
- “BOB”,如果鲍勃会赢得比赛,
- “平局”,如果比赛以平局结束。
示例
输入 #1
3 3 110 2 00 4 1010
输出 #1
ALICE BOB ALICE
注意
在示例的第一个测试用例中,
- 在 $$$1$$$-st 移动中,Alice 将使用 $$$2$$$-nd 操作来反转字符串,因为执行 $$$1$$$-st 操作无论如何都会导致她的损失。这也迫使 Bob 使用 $$$1$$$-st 操作。
- 在 $$$2$$$-nd 移动中,Bob 必须执行 $$$1$$$-st 操作,因为 $$$2$$$-nd 操作不能连续执行两次。字符串中的所有字符都是“1”,游戏结束。
在示例的第二个测试用例中,
- 在 $$$1$$$-st 移动中,Alice 必须执行 $$$1$$$-st 操作,因为该字符串当前是回文。
- 在 $$$2$$$-nd 移动中,Bob 反转了字符串。
- 在 $$$3$$$-rd 步中,Alice 必须再次执行 $$$1$$$-st 操作。字符串中的所有字符都是“1”,游戏结束。