P12530 [XJTUPC 2025] Pythagorean Cup

Alice and Bob are playing a game with $n$ Pythagorean cups (known as Fairness cups in Chinese). When drinking from a Pythagorean cup, it behaves like a regular cup as long as it is not filled to the top. If it is filled to the top, the liquid will completely flow out through the bottom hole. The structure of the Pythagorean cup is shown in the figure below.  Pythagorean Cup (Fairness Cup) In the initial phase, wine is poured into the $n$ empty Pythagorean cups in sequence. There are three possible amounts of wine that can be poured: no wine, represented by the uppercase letter $\tt{E}$; half a cup of wine, represented by the uppercase letter $\tt{H}$; and a full cup of wine, represented by the uppercase letter $\tt{F}$. Then, each time Alice and Bob can choose a $\textbf{non-empty}$ Pythagorean cup and pour all the wine from it into the cup to its right. If they choose the rightmost cup, they can simply discard it. At any moment, if a Pythagorean cup is full, it will immediately flow out and become empty. If a cup is half full and half a cup of wine is poured into it, it will overflow and become empty. Alice and Bob take turns making moves, with Alice going first. If Alice or Bob has no Pythagorean cups to choose from, the person who cannot choose Pythagorean cups loses the game. Assuming both Alice and Bob play optimally, determine who wins the game.

The input consists of a single line containing a string $S$ ($1\le |S|\le 10^6$). The length of the string $|S|$ represents the number of Pythagorean cups $n$. $S_i$ is one of the uppercase letters $\tt{EHF}$, indicating how much wine to pour into the $i$-th Pythagorean cup initially. No wine is represented by the uppercase letter $\tt{E}$; half a cup of wine is represented by the uppercase letter $\tt{H}$; and a full cup of wine is represented by the uppercase letter $\tt{F}$.

Output a single line containing a string. If Alice wins, output $\tt{Alice}$; if Bob wins, output $\tt{Bob}$.

For the first sample: Initially, half a cup of wine is poured into the $1$-st Pythagorean cup; no wine is poured into the $2$-nd cup; a full cup of wine is poured into the $3$-rd cup, which immediately flows out; half a cup of wine is poured into the $4$-th cup. After the start, the states of the $4$ cups are half full, empty, empty, and half full. At the beginning, Alice can choose the $4$-th cup and discard it; then, only the $1$-st cup is half full, and Bob can only choose the $1$-st cup to pour into the $2$-nd cup; similarly, at this point, only the $2$-nd cup is half full, and Alice can only choose the $2$-nd cup to pour into the $3$-rd cup; Bob can only choose the $3$-rd cup to pour into the $4$-th cup; Alice can only choose the $4$-th cup and discard it. At this point, Bob cannot choose any Pythagorean cup anymore and loses the game.