#arc148d. [arc148_d]mod M Game

[arc148_d]mod M Game

题目描述

黑板上有 2N2N 个整数 A1,A2,...,A2NA_1, A_2, ..., A_{2N},以及一个至少为 22 的整数 MM
Alice 和 Bob 将进行一场游戏。他们轮流执行以下操作,Alice 先开始,直到黑板上没有数字。

  • 选择一个数字并从黑板上删除它。

在游戏结束时,如果 Alice 删除的数字之和对 MM 取模等于 Bob 删除的数字之和对 MM 取模,则 Bob 获胜;否则,Alice 获胜。
如果两个玩家都采取最优策略,那么谁会获胜?

约束条件

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 2M1092 \leq M \leq 10^9
  • 0AiM10 \leq A_i \leq M - 1
  • 输入中的所有值都是整数。

输入

从标准输入读取输入数据,输入格式如下:

NN MM A1A_1 A2A_2 \dots A2NA_{2N}

输出

如果 Alice 获胜,输出 Alice;如果 Bob 获胜,输出 Bob


示例输入1

2 9
1 4 8 5

示例输出1

Alice

游戏可能进行如下:

  • Alice 删除 11
  • Bob 删除 44
  • Alice 删除 55
  • Bob 删除 88

在这种情况下,Alice 删除的数字之和对 MM 取模为 (1+5)mod9=6(1 + 5) \bmod 9 = 6,Bob 删除的数字之和对 MM 取模为 (4+8)mod9=3(4 + 8) \bmod 9 = 3。因为 636 \neq 3,Alice 获胜。


示例输入2

3 998244353
1 2 3 1 2 3

示例输出2

Bob