Problem Description

Alice and Bob are playing a game with the following rules:

• Before the game starts, a string $s$ is given.

• In each move, choose a substring $t$ of $s$. The substring $t$ must be one of 10, 100, 110, 1010. Then flip every character in $t$. For example, flipping 100 becomes 001.

• The player who cannot make a move loses the game.

Alice moves first. Assuming both players use optimal strategies, determine who will win.

Input Format

A string $s$ containing only $0$ and $1$ $(1 \leq |s| \leq 10^6)$.

Output Format

If Alice wins, output Alice. If Bob wins, output Bob.

010

Alice

1111

Bob

1010

Bob

1010001011001

Alice

Hint

For sample $1$, after choosing the substring 10 and flipping it, Bob cannot make a move.

Translated by ChatGPT 5