#P17807. [Ontak2024]受限Nim

[Ontak2024]受限Nim

题目描述

Alicja 和 Bob 玩一种修改规则后的 Nim 游戏。

初始有 nn 堆物品,第 ii 堆有 aia_i 个,另给定一个正整数 kk。双方轮流操作,Alicja 先手。

每次操作,玩家必须选择一堆,从中取走正整数个物品,且不能超过该堆的剩余数量。此外:

  • Alicja 第一次操作取走的数量不能超过 kk。
  • 从第二次操作起,每次取走的数量不能超过对方在紧接着的上一次操作中取走的数量。

无法进行合法操作的玩家输掉游戏。

双方都采取最优策略。请判断谁会获胜。

输入格式

第一行包含一个整数 tt,表示测试用例数量。

每个测试用例的第一行包含两个整数 n,kn,k。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示各堆的初始数量。

输出格式

对每个测试用例输出一行:若 Alicja 获胜,输出 Alicja;否则输出 Bob。

数据范围

$$1\le t\le10^6,\quad 1\le n\le10^6,\quad 1\le k,a_i\le10^9.$$

所有测试用例的 nn 之和不超过 10610^6。

样例

4
3 1
3 1 1
5 2
2 1 1 1 1
1 2
3
2 1
1 1
Alicja
Alicja
Alicja
Bob

子任务

额外限制 分值
k=1k=1 26
n≤10n\le10,所有测试用例的 nn 之和不超过 100100,ai≤3a_i\le3 8
n≤10n\le10,ai≤5a_i\le5 11
n=1n=1,k,ai≤100k,a_i\le100 8
n=1n=1 16
k=2k=2
kk 是 22 的幂 7
无额外限制 8