Problem Description

Lily is an interesting girl. She often plays strange games with Kaguya.

Today, they are playing a game called nim. Specifically, the rules of the nim game are as follows:

• There are several rows of chess pieces with known quantities, and the two players take turns removing any positive integer number of pieces from any row.
• Lily goes first, and the player who cannot make a move loses, i.e., the player who removes the last piece wins.

Because the optimal strategy is very simple, they quickly became bored after a few rounds. Therefore, they added a new rule based on the original rules:

• In a row with $x$ pieces, one can remove $y$ pieces if and only if $y^k \le x$.

This made the game more interesting. However, due to the complexity of the strategy, Lily often feels overwhelmed when calculating.

It can be proven that for any given state of this game, either Lily has a winning strategy or Kaguya has a winning strategy.

Thus, Lily wants you to write a program to calculate which player has a winning strategy in a given state (Lily always goes first), so she can analyze where she made mistakes during the review.

Since the curious Lily might analyze the states in detail, you need to answer her multiple queries.

Since all states are derived from the same game during the review, all queries have the same parameter $k$.

The format of the states in the queries is special, detailed in the Input Format section.

Input Format

The first line of input contains two integers $t$ and $k$, representing the number of queries and the parameter in the operations, respectively.

The following lines describe each query in turn:

The first line of each query contains an integer $n$.

The second line of each query contains $n$ integers $a_1, \dots, a_n$.

$(n, a_{1 \dots n})$ represents $\sum a_i$ rows of chess pieces, with each row containing pieces numbered from $1$ to $a_1, 1$ to $a_2, \dots, 1$ to $a_n$.

If you are familiar with game theory, you might notice that the problem can be transformed into:

• Let the Grundy value of a row with $x$ pieces be $g(x)$, and let $h(x)$ be the prefix XOR sum of $g(x)$. Determine if the XOR sum of $h(a_1) \dots h(a_n)$ is $0$.

Output Format

For each query, output a single line containing a string.

• If Lily has a winning strategy, output Lily.
• If Kaguya has a winning strategy, output Kaguya.

Sample Input and Output

Sample Input #1

3 1
2
1 5
3
1 2 3
1
3

Sample Output #1

Kaguya
Lily
Kaguya

Sample Input #2

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

Sample Output #2

Kaguya
Lily
Kaguya
Kaguya

Notes/Hints

For all test data, it is guaranteed that: $1 \le k \le 5$, $1 \le n, \sum n \le 10^5$, $1 \le a_i < 2^{60}$.

The specific restrictions for each subtask are as follows:

Special Property A: It is guaranteed that $2 \mid n$, and $a_{2k - 1} = a_{2k} - 1 \pmod{1 \le k \le \frac{n}{2}}$.

Hint: If you are getting unexpected TLE, you might want to try optimizing your time complexity.

见题面 Input 部分

见题面 Output 部分