Alice 和 Bob 正在玩弦乐游戏。
最初,他们有一些字符串 $$$t$$$。在一次移动中,第一个玩家选择 $$$t$$$ 中出现的字符 $$$c$$$ 并删除 $$$t$$$ 中出现的所有字符,从而将 $$$t$$$ 分成许多较小的字符串。然后,游戏独立地处理每个字符串 - 让移动玩家选择其中一个字符串和其中的一个字符,删除所有出现的情况并将剩余的字符串添加回游戏。
Alice总是开始游戏,然后Alice和Bob轮流走棋。无法移动的玩家(因为没有剩下的绳子)就输了。
Alice 和 Bob 过去总是以字符串 $$$s$$$ 开头,但最近他们发现这变得太无聊了。现在,在每个游戏之前,他们选择两个整数 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le |s|$$$ 并使用字符串 $$$s_{l} s_{l+1} s_{l+2} \ldots s_{r}$$$ 来玩游戏。
给定每个游戏的字符串 $$$s$$$ 和整数 $$$l$$$、$$$r$$$。找出谁将赢得每场比赛,假设他们很聪明并且表现最佳。
输入
第一行包含由小写英文字母组成的字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$)。这是 Alice 和 Bob 用来开始的字符串。
第二行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$) — 要分析的游戏数量。
接下来的 $$$m$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le |s|$$$) - 字符串 $$$s$$$ 中起始子字符串的边界。
输出
对于每个游戏,输出一行,其中包含获胜者的姓名 - 分别为“Alice”或“Bob”。
示例
输入 #1
aaab 2 1 2 1 4
输出 #1
Alice Bob
输入 #2
aaccbdb 2 5 7 1 7
输出 #2
Alice Alice
注意
在第一个示例中,
1. 在第一个游戏中,选择了字符串“aa”。 Alice 删除了字符“a”,而 Bob 无法移动。
2. 在第二个游戏中,选择了字符串“aaab”。无论Alice要删除哪个角色,Bob都会删除另一个角色,而Alice将无法移动。
在第二个示例中,Alice 赢得了游戏“bdb”和“aaccbdb”。
为了赢得游戏“bdb”,Alice 可以擦除符号“d”,然后游戏独立地在字符串“b”和“b”上进行。鲍勃删除了其中一个字符串,爱丽丝删除了另一个字符串,鲍勃无法移动。
要赢得游戏“aaccbdb”,Alice 可以擦除符号“d”,然后游戏独立于字符串“aaccb”和“b”进行。可以证明,无论移动什么,剩下的游戏只能在 $$$4$$$ 移动中完成,因此 Bob 在这之后将无法移动。