/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
正整数 N, M があります。ここで N \lt M が成り立ちます。
Alice と Bob がゲームをします。2 人は 1, 2, \dots, N が書かれたカードを 1 枚ずつ、合計 N 枚のカードをそれぞれ持っています。
ゲームでは Alice を先攻として 2 人が交互に「手札を 1 枚選び、場に出す」という操作を繰り返します。
カードが場に出た直後に、今まで場に出たカードに書かれている数の総和が M で割り切れる状態になったら、直前にカードを出した人の負け、そうでない人の勝ちとなります。
上の条件を満たすことなく両者が持っているカードを全て出し切った場合は Alice の勝ちとなります。
双方が最適に行動した時、Alice と Bob のどちらが勝ちますか？
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq N \lt M \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N M
出力
T 行出力せよ。i 行目には i 番目のテストケースへの答えを出力せよ。
各テストケースでは、双方が最適に行動した時に Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を出力せよ。
入力例 1
8 2 3 3 6 5 9 45 58 39 94 36 54 74 80 61 95
出力例 1
Alice Alice Bob Bob Alice Bob Bob Alice
1 番目のテストケースにおいて、ゲームの進行例を挙げると以下のようになります。
- はじめ、Alice と Bob はともに 1 が書かれたカードと 2 が書かれたカードの 2 枚を持っている。
- Alice が 1 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 1 であり、これは 3 で割り切れないので Alice の負けにはならない。
- Bob が 1 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 2 であり、これは 3 で割り切れないので Bob の負けにはならない。
- Alice が 2 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 4 であり、これは 3 で割り切れないので Alice の負けにはならない。
- Bob が 2 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 6 であり、これは 3 で割り切れるので、Bob の負け、Alice の勝ちとなる。
1 番目のテストケースでは、Bob がどのように行動しても Alice が勝つことが出来ます。
Score : 600 points
Problem Statement
There are positive integers N and M, where N \lt M.
Alice and Bob will play a game. Each player has N cards with 1, 2, \dots, N written on them, one for each number.
Starting with Alice, the two players take turns repeatedly performing this action: choose one card from their hand and play it onto the table.
Immediately after a card is played onto the table, if the sum of the numbers on the cards that have been played so far is divisible by M, the player who just played the card loses, and the other player wins.
If both players play all their cards without satisfying the above condition, Alice wins.
Who will win, Alice or Bob, when both play optimally?
You are given T test cases. Solve each of them.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N \lt M \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format. Here, \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N M
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
For each test case, if Alice wins when both play optimally, print Alice; if Bob wins, print Bob.
Sample Input 1
8 2 3 3 6 5 9 45 58 39 94 36 54 74 80 61 95
Sample Output 1
Alice Alice Bob Bob Alice Bob Bob Alice
In the first test case, the game could proceed as follows.
- Initially, both Alice and Bob have two cards: the card with 1 and the card with 2.
- Alice plays the card with 1.
- The sum of the numbers on the cards played so far is 1, which is not divisible by 3, so Alice does not lose.
- Bob plays the card with 1.
- The sum is now 2, which is not divisible by 3, so Bob does not lose.
- Alice plays the card with 2.
- The sum is now 4, which is not divisible by 3, so Alice does not lose.
- Bob plays the card with 2.
- The sum is now 6, which is divisible by 3, so Bob loses and Alice wins.
In the first test case, no matter how Bob plays, Alice can win.