D - Stones Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個の石の山があり、それぞれの山に 1 から N までの番号が割り振られています。山 i にある石の数は a_i です。また、N 個の数 b_i が与えられます。 Alice と Bob はゲームをします。Alice が先手として以下の操作を交互に行い、操作できなくなった方が負けです。

  • ある石の山 i を選びます。ある非負整数 k を選び、山 i から石を b_i^k 個取ります。取った後の石の数が負になってはいけません。

両者が最適にゲームをしたとき、どちらが勝つでしょうか。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq a_i, b_i \leq 10^9
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1
a_2 b_2
\vdots
a_N b_N

出力

Alice が勝つときは Alice と、Bob が勝つときは Bob と一行で出力せよ。

入力例1

2
10 3
7 4

出力例1

Bob

入力例2

16
903 5
246 38
884 12
752 10
200 17
483 6
828 27
473 21
983 35
953 36
363 35
101 3
34 23
199 8
134 2
932 28

出力例2

Alice

入力例3

16
35 37
852 17
789 37
848 40
351 27
59 32
271 11
395 20
610 3
631 33
543 14
256 28
48 8
277 24
748 38
109 40

出力例3

Bob