Modified Nim Game

Lily and Kaguya are playing a modified version of the classic Nim game. In this game, there are several piles of stones; each pile contains a known number of stones. Players take turns removing stones from any one pile, with Lily always moving first. A move consists of removing a positive integer number of stones \(y\) from a pile containing \(x\) stones, under the condition that \(y^k \le x\), where \(k\) is a fixed parameter for all queries. The player who removes the last stone wins.

After a few rounds, the game became too predictable due to the simple optimal strategy. To spice things up, a new rule was added: from a pile with \(x\) stones, a player can remove \(y\) stones if and only if \(y^k \le x\). Although this makes the game more interesting, it also complicates the strategy.

It can be proven that for any given game position, either Lily has a winning strategy or Kaguya has a winning strategy. Lily now wishes to analyze several positions (all derived from the same game, and thus with the same \(k\) in effect) by asking multiple queries. In each query, you are given a subarray of the piles, and your task is to determine which player, assuming optimal play, will win the game.

inputFormat

The first line contains three integers \(n\), \(q\), and \(k\) \((1 \le n, q \le 10^5, 1 \le k \le 10)\), representing the number of piles, the number of queries, and the fixed parameter \(k\), respectively.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 10^4)\), where \(a_i\) is the number of stones in the \(i\)-th pile.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) \((1 \le l \le r \le n)\). For each query, consider the subarray of piles from index \(l\) to \(r\) (inclusive) and determine who wins under optimal play.

outputFormat

For each query, output a single line containing either "Lily" if the first player (Lily) has a winning strategy, or "Kaguya" if the second player (Kaguya) has a winning strategy.

sample

3 3 2
1 2 3
1 1
1 2
1 3

Lily
Lily
Kaguya