配点 : $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 を出力せよ。

2 9
1 4 8 5

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 の勝ちです。

3 998244353
1 2 3 1 2 3

Bob