P10014 [CTT Mutual Test 2023] Cocoon

Lily is an interesting girl. She often plays some strange games with Kaguya. Today they are playing a game called nim. Specifically, the rules of nim are as follows: - There are several piles of a known number of stones. Two players take turns removing any positive number of stones from any one pile. - Lily moves first. The player who cannot make a move loses, i.e. the one who removes the last stone wins. Because the optimal strategy is very simple, after a few rounds they started to feel bored. So, based on the original rules, they added one more rule: - From a pile with $x$ stones, you can remove $y$ stones if and only if $y^k \le x$. Now the game becomes interesting. However, since the strategy is rather complicated, Lily often finds it hard to compute. It can be proven that for any position of this game, either Lily has a winning strategy, or Kaguya has a winning strategy. So Lily wants you to write a program to determine who has a winning strategy in a given position (Lily always moves first), so that she can analyze which move was a mistake when reviewing the game. Since the curious Lily may analyze positions in detail, you need to answer multiple queries. Because all positions come from reviewing the same game, the parameter $k$ is the same for all queries. **The queried positions have a special form. See the input format for details.**

The first line contains two integers $t, k$, representing the number of queries and the parameter in the move rule. Then follow the queries. For each query: The first line contains an integer $n$. The second line contains $n$ integers $a_1, \dots, a_n$. $(n, a_{1 \dots n})$ means there are $\sum a_i$ piles of stones, and the numbers of stones in each pile are respectively $1 \dots a_1, 1 \dots a_2, \dots, 1 \dots a_n$. If you are familiar with game theory, it is not hard to see that the problem can be transformed into: - Let the [Grundy value](https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem) of a pile with $x$ stones be $g(x)$, and let $h(x)$ be the prefix xor sum of $g(x)$. Determine whether the xor of $h(a_1) \dots h(a_n)$ is $0$.

For each query, output one string per line. - If Lily has a winning strategy, output `Lily`. - If Kaguya has a winning strategy, output `Kaguya`.

For samples 3, 4, and 5, see the attached file. For all testdata, it is guaranteed that $1 \le k \le 5$, $1 \le n, \sum n \le 10^5$, and $1 \le a_i \lt 2^{60}$. The detailed limits for each subtask are shown in the table below: | Subtask ID | $n$ | $k$ | $a_i$ | Special Property | Score | | ---------- | -------------------------- | --------------- | -------------- | ---------------- | ----- | | 1 | $\sum n \le 10^5$ | $k = 1$ | $a_i < 2^{60}$ | | $5$ | | 2 | $\sum n \le 10^5$ | $2 \le k \le 5$ | $a_i < 2^{16}$ | | $5$ | | 3 | $\sum n \le 10^5$ | $2 \le k \le 5$ | $a_i < 2^{22}$ | | $10$ | | 4 | $\sum n \le 10^3$, $n = 2$ | $2 \le k \le 3$ | $a_i < 2^{32}$ | A | $10$ | | 5 | $\sum n \le 10^3$ | $2 \le k \le 5$ | $a_i < 2^{32}$ | A | $10$ | | 6 | $\sum n \le 10^5$ | $k = 2$ | $a_i < 2^{60}$ | A | $10$ | | 7 | $\sum n \le 10^5$ | $k = 3$ | $a_i < 2^{60}$ | A | $10$ | | 8 | $\sum n \le 10^3$ | $k = 2$ | $a_i < 2^{32}$ | | $10$ | | 9 | $\sum n \le 10^3$ | $k = 3$ | $a_i < 2^{32}$ | | $10$ | | 10 | $\sum n \le 10^5$ | $1 \le k \le 5$ | $a_i < 2^{60}$ | | $20$ | Special property A: it is guaranteed that $2 \mid n$, and $a_{2k - 1} = a_{2k} - 1 \pod{1 \le k \le \frac n 2}$. Hint: If you get an unexpected TLE, you may try to optimize your time complexity. > Slightly adjusted a few wordings in the statement. > > Please refer to QOJ for the original statement. Translated by ChatGPT 5