P12530 [XJTUPC 2025] 公道杯

Alice 和 Bob 在玩一个游戏，在他们面前摆着 $n$ 个公道杯（在欧洲称为毕达哥拉斯杯）。用公道杯饮酒之时，只要不斟满，则与常杯无异。若斟满，则酒会从底孔完全流光。公道杯的结构如下图。  公道杯（毕达哥拉斯杯） 在初始阶段，向 $n$ 个空公道杯依次倒入酒，可能倒入如下三种分量的酒：不倒酒，用大写英文字母 $\tt{E}$ 表示；半杯酒，用大写英文字母 $\tt{H}$ 表示；一整杯酒，用大写英文字母 $\tt{F}$ 表示。 然后，每一次 Alice 和 Bob 可以选择一个 **非空** 的公道杯，将它之中的所有酒倒入它右边的公道杯中。若选择最右边的公道杯，则可以直接将其倒掉。 在公道杯的任意时刻，当酒满了的时候，会立刻流光变成空杯。若一个公道杯是半满的状态，向其中再倒半杯酒，则会因为满了而流空。 Alice 和 Bob 依次进行操作，Alice 先进行第一次操作。当 Alice 或 Bob 在场上没有可以选取的公道杯时，则无法选取公道杯的人输掉了游戏。假设 Alice 和 Bob 都非常聪明，采取最优做法，问 Alice 和 Bob 谁获胜。

输入共一行一个字符串 $S$ ($1\le |S|\le 10^6$)。字符串的长度 $|S|$ 就是公道杯的个数 $n$。 $S_i$ 为大写英文字母 $\tt{EHF}$ 中的一个，表示第 $i$ 个公道杯在最开始要倒多少酒。不倒酒，用大写英文字母 $\tt{E}$ 表示；半杯酒，用大写英文字母 $\tt{H}$ 表示；一整杯酒，用大写英文字母 $\tt{F}$ 表示。

输出共一行一个字符串。 若 Alice 获胜输出 $\tt{Alice}$；若 Bob 获胜输出 $\tt{Bob}$。

对于第一组样例：最开始时，对第 $1$ 个公道杯倒入半杯酒；第 $2$ 个公道杯不倒酒；第 $3$ 个公道杯倒入一整杯酒，随即立刻流空；第 $4$ 个公道杯倒入半杯酒。即开始后，$4$ 个公道杯的状态为半满、空、空、半满。 Alice 开始时可以选择第 $4$ 个公道杯，直接将其倒掉；随后，只有第 $1$ 个公道杯是半满的，Bob 只能选择第 $1$ 个公道杯，倒入第 $2$ 个公道杯中；同样的，此时只有第 $2$ 个公道杯是半满的，Alice 只能选择第 $2$ 个公道杯，倒入第 $3$ 个公道杯中；Bob 只能选择第 $3$ 个公道杯，倒入第 $4$ 个公道杯中；Alice 只能选择第 $4$ 个公道杯，直接将其倒掉。此时，Bob 无法再选择公道杯，输掉了游戏。