/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
黒板に 2N 個の整数 A_1, A_2, ..., A_{2N} が書かれています。また、2 以上の整数 M があります。
Alice と Bob はゲームをします。
ゲームは Alice を先攻として、黒板の上の数が全てなくなるまで次の操作を交互に行います。
- 数を 1 個選び、その数を黒板から消す。
ゲームを終了した時点で、(Alice が消した数の和) \text{mod }M と (Bob が消した数の和) \text{mod }M が一致していれば Bob の勝ち、そうでない場合は Alice の勝ちです。
両者が最善を尽くしたとき、どちらが勝ちますか？
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 10^9
- 0 \leq A_i \leq M - 1
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A_1 A_2 \dots A_{2N}
出力
Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を出力せよ。
入力例 1
2 9 1 4 8 5
出力例 1
Alice
ゲームの進行例として次のようなものが考えられます。
- Alice が 1 を消す。
- Bob が 4 を消す。
- Alice が 5 を消す。
- Bob が 8 を消す。
このように進んだ場合、(Alice が消した数の和) \text{mod }M は (1 + 5) \bmod 9 = 6, (Bob が消した数の和) \text{mod }M は (4 + 8) \bmod 9 = 3 で、6 \neq 3 なので Alice の勝ちです。
入力例 2
3 998244353 1 2 3 1 2 3
出力例 2
Bob
Score : 700 points
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