201483: [AtCoder]ARC148 D - mod M Game

Problem Statement

There are $2N$ integers $A_1, A_2, ..., A_{2N}$ written on a blackboard, and an integer $M$ at least $2$.
Alice and Bob will play a game. They will alternately perform the following operation, with Alice going first, until there is no number on the blackboard.

• Choose a number and delete it from the blackboard.

At the end of the game, if the sum of numbers deleted by Alice modulo $M$ equals the sum of numbers deleted by Bob modulo $M$, Bob wins; otherwise, Alice wins.
Which player will win if both plays optimally?

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 10^9$
• $0 \leq A_i \leq M - 1$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_{2N}$

Output

If Alice wins, print Alice; if Bob wins, print Bob.

Sample Input 1

2 9
1 4 8 5

Sample Output 1

Alice

The game may proceed as follows.

• Alice deletes $1$.
• Bob deletes $4$.
• Alice deletes $5$.
• Bob deletes $8$.

In this case, the sum of numbers deleted by Alice modulo $M$ is $(1 + 5) \bmod 9 = 6$, and the sum of numbers deleted by Bob modulo $M$ is $(4 + 8) \bmod 9 = 3$. Since $6 \neq 3$, Alice wins.

Sample Input 2

3 998244353
1 2 3 1 2 3

Sample Output 2

Bob