Problem Description

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

• A string \( s \) is given at the start of the game.

• In each move, a player selects a substring \( t \) of \( s \). The substring \( t \) can only be one of 10, 100, 110, or 1010. Each character in \( t \) is then reversed, for example, 100 becomes 001.

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

Alice moves first. Determine who wins the game if both players play optimally.

Input Format

A string \( s \) consisting only of characters 0 and 1 with \( 1 \leq |s| \leq 10^6 \).

Output Format

Output Alice if Alice wins, or Bob if Bob wins.

Sample Input and Output

Sample Input #1

010

Sample Output #1

Alice

Sample Input #2

1111

Sample Output #2

Bob

Sample Input #3

1010

Sample Output #3

Bob

Sample Input #4

1010001011001

Sample Output #4

Alice

Notes

For Sample #1, Alice can choose the substring 10 and reverse it, leaving Bob with no valid moves.

见题面 Input 部分

见题面 Output 部分