Problem Description

There are $ N $ piles of coins.

The piles are numbered from $ 1 $ to $ N $, and the $ i $th pile consists of $ a_i $ coins.

Consider the following two-player game using these piles of coins:

• Players are divided into first and second.
• Starting from the first player, each player takes turns. On their turn, the player performs the following two actions in sequence:
  1. Declare a positive integer $ x $ not exceeding $ K $.
  However, starting from the second turn, the player must declare an integer $ x $ that is smaller than the integer declared on their previous turn.
  2. Choose one pile containing at least $ x $ coins and remove $ x $ coins from that pile.
  If no such pile exists, the game ends there, and the other player wins.

Chinatsu and Akari decided to play this game, with Chinatsu as the first player and Akari as the second player, for $ M $ rounds.

However, after each game ends, the coins removed during that game are returned to their original piles.

Since Chinatsu and Akari both play optimally to win, and the number of coins in each pile at the start of the game does not change, the outcome of the game is not interesting.

Therefore, they decided to increase the number of coins in the $ b_i $th pile by $ c_i $ after the $ i $th game ($1 \leq i \leq M - 1$), after returning the removed coins to their original piles.

Determine which player wins each of the $ M $ games.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ M $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ b_1 $ $ c_1 $ $ : $ $b_{M\ -\ 1}$ $c_{M\ -\ 1}$

Output Format

On the $ i $th line, output Chinatsu if Chinatsu (the first player) wins the $ i $th game, or Akari if Akari (the second player) wins the $ i $th game.

Sample Input and Output

Sample Input #1

1 8 1
7

Sample Output #1

Chinatsu

Sample Input #2

1 1 1
2

Sample Output #2

Akari

Sample Input #3

5 7 3
83795 19140 82706 34385 26675
2 74621
3 60951

Sample Output #3

Chinatsu
Akari
Chinatsu

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq M \leq 10^5$
• $1 \leq a_i \leq 10^9$
• $1 \leq b_i \leq N$
• $1 \leq c_i \leq 10^9$

Partial Points

If you solve the dataset that satisfies all of the following additional constraints, you will be awarded $ 30 $ points:

• $ N = 1 $
• $ M = 1 $

If you solve the dataset without the additional constraints, you will be awarded an additional $ 370 $ points.

Sample Explanation 1

Chinatsu, being the first player, can remove all the coins from the only pile on her first turn. On Akari's next turn, Akari cannot choose any pile with enough coins to match her declaration, so Chinatsu wins the game. This input example satisfies the additional constraints for partial points.

Sample Explanation 2

Both players can only declare $ 1 $. On Chinatsu's first turn, she removes $ 1 $ coin from the pile. On Akari's next turn, Akari removes the last $ 1 $ coin. On Chinatsu's second turn, she cannot choose any pile with enough coins, so Akari wins the game. This input example satisfies the additional constraints for partial points.

见题面 Input 部分

见题面 Output 部分