24656번 - Destructive Game 다국어

There are $N$ stone piles, numbered by sequential integers from $1$ to $N$. The $i$-th pile contains $a_i$ stones. Additionally, each pile $i$ has an integer $b_i$ associated with it.

Alice and Bob play the following game using those stone piles.

They are alternately performing the following operation: choose pile $i$ and a nonnegative integer $k$ such that $b_i^k$ is not greater than the current number of stones in pile $i$, and remove $b_i^k$ stones from pile $i$. If a player cannot do that on their turn, the opposite player wins.

Alice moves first. Determine who will win if both players are playing optimally.

The first line of input contains one integer $N$ ($1 \le N \le 10^5$), the number of piles. The $i$-th of the following $N$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$): the initial number of stones in the $i$-th pile and the integer associated with it, respectively.

If Alice wins the game when both sides are playing optimally, print "Alice". Otherwise, print "Bob".