Binary String Flipping Game

Alice and Bob play a turn‐based game on a binary string s. At the start, you are given the string s.

On each turn, the current player must choose a substring t of s such that t is exactly one of the following:

• $10$
• $100$
• $110$
• $1010$

Then, the player flips every digit of t (i.e. replaces every 1 with 0, and every 0 with 1). For example, $100$ becomes $001$ after flipping.

A move is only allowed if it does not cause the mover to eventually face a losing position — in other words, both players play optimally and will avoid moves that would immediately turn the game into a loss for themselves.

If a player has no valid moves on their turn, they lose. Alice moves first. Determine which player will win under optimal play.

inputFormat

The input consists of a single line containing a binary string s (i.e. a string consisting only of characters 0 and 1). It is guaranteed that the length of s is relatively small so that a complete search is feasible.

outputFormat

Output a single line containing Alice if Alice can force a win under optimal play, and Bob otherwise.

sample

10

Alice