B - All Minus Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

黒板に N 個の非負整数 A_1,A_2,\dots,A_N が書かれています。

Alice と Bob がゲームをします。Alice から始めて以下の操作を交互に行い、黒板に書かれている整数を 0 個にした方が勝ちです。

  • 操作を行う時点で黒板に書かれている最小の非負整数を m とする。
    • m > 0 のとき、1 以上 m 以下の正整数 x を選ぶ。黒板に書かれている全ての整数をそれぞれ今の値から x 引いた数に書き換える。
    • m = 0 のとき、黒板に書かれている 0 のうち、1 個以上を削除する。

両者が勝つために最善な行動をしたとき、勝つのがどちらか判定してください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • 0 \le A_i \le 10^9
  • 全てのテストケースに対する N の総和は 2 \times 10^5 以下
  • 入力は全て整数

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N
A_1 A_2 \dots A_N

出力

T 行出力せよ。i 行目には \mathrm{case}_i について、Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を出力せよ。

入力例 1

5
1
2
3
1 1 1
4
1 2 3 4
7
3 1 4 1 5 9 2
3
218 503 2026

出力例 1

Alice
Bob
Bob
Bob
Alice

1 個目のテストケースについて、あり得るゲームの進行としては、以下のようなものが考えられます。

  • 始め、黒板には 2 が書かれている。
  • Alice が x = 1 を選ぶ。黒板には 1 が書かれている。
  • Bob が x = 1 を選ぶ。黒板には 0 が書かれている。
  • Alice が 0 を 1 個選び削除する。黒板には何も書かれていない。

両者が勝つために最善な行動をしたとき、勝つのは Alice です。

2 個目のテストケースについて、あり得るゲームの進行としては、以下のようなものが考えられます。

  • 始め、黒板には 1,1,1 が書かれている。
  • Alice が x = 1 を選ぶ。黒板には 0,0,0 が書かれている。
  • Bob が 0 を 1 個選び削除する。黒板には 0,0 が書かれている。
  • Alice が 0 を 1 個選び削除する。黒板には 0 が書かれている。
  • Bob が 0 を 1 個選び削除する。黒板には何も書かれていない。

両者が勝つために最善な行動をしたとき、勝つのは Bob です。

Score : 400 points

Problem Statement

There are N non-negative integers A_1,A_2,\dots,A_N written on a blackboard.

Alice and Bob play a game. Starting with Alice, they alternately perform the following operation, and the player who reduces the number of integers written on the blackboard to 0 wins.

  • Let m be the minimum non-negative integer currently written on the blackboard.
    • If m > 0, choose a positive integer x between 1 and m, inclusive. Replace every integer written on the blackboard with its current value minus x.
    • If m = 0, erase one or more of the 0s written on the blackboard.

Determine who wins when both players play optimally to win.

T test cases are given; solve each of them.

Constraints

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • 0 \le A_i \le 10^9
  • The sum of N over all test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A_1 A_2 \dots A_N

Output

Output T lines. The i-th line should contain Alice if Alice wins in \mathrm{case}_i, or Bob if Bob wins.

Sample Input 1

5
1
2
3
1 1 1
4
1 2 3 4
7
3 1 4 1 5 9 2
3
218 503 2026

Sample Output 1

Alice
Bob
Bob
Bob
Alice

For the first test case, one possible game progression is as follows:

  • Initially, 2 is written on the blackboard.
  • Alice chooses x = 1. Now 1 is written on the blackboard.
  • Bob chooses x = 1. Now 0 is written on the blackboard.
  • Alice chooses and erases one 0. Now nothing is written on the blackboard.

When both players play optimally to win, Alice wins.

For the second test case, one possible game progression is as follows:

  • Initially, 1,1,1 are written on the blackboard.
  • Alice chooses x = 1. Now 0,0,0 are written on the blackboard.
  • Bob chooses and erases one 0. Now 0,0 are written on the blackboard.
  • Alice chooses and erases one 0. Now 0 is written on the blackboard.
  • Bob chooses and erases one 0. Now nothing is written on the blackboard.

When both players play optimally to win, Bob wins.