Stone Game II

Problem Description

Alice and Bob are playing a game about stones.

There are $n$ piles of stones, where the $i$-th pile initially contains $a_i$ stones.

They take turns performing one of the following operations, starting with Alice:

• Split a pile with an odd number of stones into two non-empty piles.
• Merge two piles with an even number of stones into one pile.

The player who cannot make any move loses.

Assuming both Alice and Bob play optimally, who will win the game?

Input Format

The first line contains an integer $n$ ($1\le n \le 10^6$).

The second line contains $n$ positive integers $a_1, \dots, a_n$ ($1\le a_1, \dots, a_n \le 10^9$).

Output Format

Alice or Bob, indicating the final winner.

Sample Input

2
2 2

Sample Output

Alice