Neo-Nim
Обмеження: 2 сек., 512 МіБ
There are \(n\) piles of stones. The \(i\)-th pile initially contains \(a_i\) stones. Additionally, an integer \(k\) is given.
Ana and Bob play a game with these stones, alternating turns with Ana going first. The moves are defined as follows.
Ana chooses an integer \(x\) such that \(2 \le x \le k\) and a pile containing at least \(x\) stones, then removes exactly \(x\) stones from it.
Bob chooses a pile containing at least one stone and removes exactly one stone from it.
The player who cannot make a move loses. Determine the winner assuming both players play optimally.
Вхідні дані
The first line contains an integer \(t\) – the number of test cases.
The first line of each test case contains two integers \(n\) and \(k\) – the number of piles and the maximum limit for Ana’s move.
The second line of each test case contains \(n\) integers \(a_i\) – the number of stones in each pile.
Вихідні дані
For each test case, output Ana if Ana wins, and
Bob if Bob wins.
Обмеження
\(1 \le n \le 10^5\),
\(2 \le k \le 10^5\),
\(1 \le a_i \le 10^5\),
the sum of \(n\) over all test cases does not exceed \(3 \cdot 10^5\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 3 2 2 5 8 4 3 2 2 4 5 1 5 2 | Bob Bob Ana |
Примітки
In the first sample, \(n = 3, k = 2, a = (2, 5, 8)\).
One of the possible game scenarios could be as follows.
Ana removes two stones from the third pile. After this move \(a\) becomes \((2, 5, 6)\).
Bob removes one stone from the first pile. After this move \(a\) becomes \((1, 5, 6)\).
Ana removes two stones from the second pile. After this move \(a\) becomes \((1, 3, 6)\).
Bob removes one stone from the third pile. After this move \(a\) becomes \((1, 3, 5)\).
Ana removes two stones from the third pile. After this move \(a\) becomes \((1, 3, 3)\).
Bob removes one stone from the third pile. After this move \(a\) becomes \((1, 3, 2)\).
Ana removes two stones from the second pile. After this move \(a\) becomes \((1, 1, 2)\).
Bob removes one stone from the third pile. After this move \(a\) becomes \((1, 1, 1)\).
It is Ana’s turn now, but she cannot make a move. Ana loses and Bob wins.
In the first sample, Bob wins.
In the second sample, Bob wins.
In the third sample, Ana wins.
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|