题目描述

Lily 是一个有趣的女孩子。她经常和 Kaguya 玩一些奇怪的游戏。

今天她们在玩一个名为 nim 的游戏。具体地，nim 游戏的规则如下：

• 有若干排数目已知的棋子，两人轮流从任意一排移除任意正整数枚棋子。
• Lily 先手，无法操作者负，即移除最后一枚棋子者获胜。

因为其最优策略非常简单，所以几局过后，她们就开始感到无趣了。于是，她们在原有规则的基础上增加了一条规则：

• 在一排 $x$ 枚棋子中可以移除 $y$ 枚，当且仅当 $y^k \le x$。

这下游戏变得有趣了。不过，由于策略比较复杂，Lily 在计算的时候常常感到力不从心。

可以证明，这个游戏的任意一个局面都满足：要么 Lily 有必胜策略，要么 Kaguya 有必胜策略。

于是，Lily 想请你编写一个程序来计算某个局面下谁有必胜策略（Lily 总是先手），以便复盘时分析哪次操作失误了。

由于求知欲旺盛的 Lily 可能会对局面进行比较细致的分析，所以你需要回答她的多次询问。

由于所有局面都是复盘同一局游戏时衍生出来的，所以所有询问的参数 $k$ 都相同。

本题询问的局面形式比较特殊，详见输入格式。

输入格式

输入的第一行包含两个整数 $t, k$，分别表示询问次数和操作中的参数。

接下来依次输入每次询问，对于每次询问：

输入的第一行包含一个整数 $n$。

输入的第二行包含 $n$ 个整数 $a_1, \dots, a_n$。

$(n, a_{1 \dots n})$ 表示有 $\sum a_i$ 排棋子，各排所含棋子数分别为 $1 \dots a_1, 1 \dots a_2, \dots, 1 \dots a_n$。

如果你对博弈论比较熟悉的话，不难发现题意可以转化为：

• 记一排 $x$ 个棋子的 Grundy value 为 $g(x)$，设 $h(x)$ 为 $g(x)$ 的前缀异或和，求 $h(a_1) \dots h(a_n)$ 的异或和是否为 $0$。

输出格式

对于每次询问输出一行一个字符串。

• 若 Lily 有必胜策略，输出 Lily；
• 若 Kaguya 有必胜策略，输出 Kaguya。

3 1
2
1 5
3
1 2 3
1
3

Kaguya
Lily
Kaguya

4 2
2
1 2
2
1 3
3
5 6 7
1
3

Kaguya
Lily
Kaguya
Kaguya

提示

样例三、四、五见下发文件。

对于所有测试数据保证：$1 \le k \le 5$，$1 \le n, \sum n \le 10^5$，$1 \le a_i \lt 2^{60}$。

每个子任务的具体限制见下表：

子任务编号	$n$	$k$	$a_i$	特殊性质	分值
1	$\sum n \le 10^5$	$k = 1$	$a_i < 2^{60}$		$5$
2		$2 \le k \le 5$	$a_i < 2^{16}$
3			$a_i < 2^{22}$		$10$
4	$\sum n \le 10^3$，$n = 2$	$2 \le k \le 3$	$a_i < 2^{32}$	A
5	$\sum n \le 10^3$	$2 \le k \le 5$
6	$\sum n \le 10^5$	$k = 2$	$a_i < 2^{60}$
7		$k = 3$
8	$\sum n \le 10^3$	$k = 2$	$a_i < 2^{32}$
9		$k = 3$
10	$\sum n \le 10^5$	$1 \le k \le 5$	$a_i < 2^{60}$		$20$

特殊性质 A：保证 $2 \mid n$，且 $a_{2k - 1} = a_{2k} - 1 \pod{1 \le k \le \frac n 2}$。

提示：如果你得到了预期之外的 TLE，你或许可以尝试优化你的时间复杂度。

微调了题面里的几处用词（）

原题面请以 QOJ 为准（）