AT_agc063_a.[AGC063A] Mex Game

给定一个由 A 和 B 组成、长度为 $N+1$ 的字符串 $S = S_0 S_1 \cdots S_N$。对于每个 $k=1,2,\ldots,N$，请解决以下问题：

Alice 和 Bob 使用集合 $X$ 进行游戏。$X$ 初始为空集，接下来按照 $t=1,2,\ldots,k$ 的顺序进行如下操作：

• 当 $t$ 为奇数时，Alice 选择一个非负整数 $x$，并将 $X$ 替换为 $X \cup \{x\}$。
• 当 $t$ 为偶数时，Bob 选择一个非负整数 $x$，并将 $X$ 替换为 $X \cup \{x\}$。

当 $k$ 次操作全部结束后，记 $x = \mathrm{mex}(X)$，如果 $S_x$ 是 A，则 Alice 获胜；如果 $S_x$ 是 B，则 Bob 获胜。注意，由于 $X$ 的元素个数不超过 $k$，所以 $x = \mathrm{mex}(X) \leq k$ 恒成立（因此 $S_x$ 一定存在）。

请输出在双方都采取最优策略的情况下，最终的胜者名字。

$\mathrm{mex}(X)$ 是什么？对于一个由非负整数组成的有限集合 $X$，$\mathrm{mex}(X)$ 定义为不属于 $X$ 的最小非负整数 $x$。

输入通过标准输入给出，格式如下：

$N$ $S$

输出 $N$ 行。第 $i$ 行输出当 $k=i$ 时，双方都采取最优策略时的胜者名字（Alice 或 Bob）。

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $S$ 是由 A 和 B 组成的长度为 $N+1$ 的字符串。

样例解释 1

以下是 $k=1$ 时游戏的一个进行示例：

• Alice 选择 $x=10$。
• $\mathrm{mex}(X) = \mathrm{mex}(\{10\}) = 0$，$S_0$ 是 A，所以 Alice 获胜。

以下是 $k=2$ 时游戏的一个进行示例：

• Alice 选择 $x=2$。
• Bob 选择 $x=0$。
• $\mathrm{mex}(X) = \mathrm{mex}(\{0,2\}) = 1$，$S_1$ 是 B，所以 Bob 获胜。

由 ChatGPT 4.1 翻译