問題文

コインの山が N 個あります。

山には 1 から N までの番号が振られており、i 番目の山は a_i 枚のコインからなります。

これらのコインの山を使った以下のような 2 人ゲームを考えます。

• プレイヤーは先攻と後攻に分かれる。
• 先攻からスタートして、各プレイヤーに交互に手番が回る。手番では以下の 2 つの操作を順に実行する。
  1. K 以下の正整数 x を宣言する。
     ただし、互いに 2 回目以降の手番では、 直前の自分の手番で宣言した整数よりも小さい x を宣言してはいけない。
  2. x 枚以上のコインを含む山を 1 個選び、その山からコインを x 枚取り除く。
     そのような山が存在しない場合、ゲームはそこで終了し、もう一方のプレイヤーがゲームに勝つ。

ちなつさんとあかりさんはこのゲームを、ちなつさんが先攻、あかりさんが後攻で M 回繰り返すことにしました。

ただし 1 回のゲームが終了するごとに、そのゲームで取り除いたコインは元あった山に戻すものとします。

ところで、ちなつさんとあかりさんはお互い勝つために最適に行動するため、ゲーム開始時の各山のコインの枚数に変化がなければ、ゲームの勝敗は変わらず面白くありません。

そこで 2 人は、i (1 \leq i \leq M - 1) 回目のゲームが終わり、取り除いたコインを元の山に戻したあとに、b_i 番目の山のコインを c_i 枚増やすことにしました。

M 回それぞれのゲームで、ちなつさんとあかりさんのどちらが勝つかを判定してください。

制約

• 入力は全て整数である
• 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

部分点

以下の追加制約を全て満たすデータセットに正解した場合は、30 点が与えられる。

• N = 1
• M = 1

追加制約のないデータセットに正解した場合は、上記とは別に 370 点が与えられる。

入力例 1

1 8 1
7

出力例 1

Chinatsu

先攻であるちなつさんは最初の手番で、唯一の山の全てのコインを取り除くことができます。
このとき次のあかりさんの手番で、あかりさんはどのような正整数を宣言しても、それ以上の枚数のコインを含む山を選ぶことができません。
従って、ちなつさんがゲームに勝利します。
この入力例は部分点の追加制約を満たしています。

入力例 2

1 1 1
2

出力例 2

Akari

お互い 1 だけを宣言することができます。
このとき最初のちなつさんの手番で、ちなつさんは山から 1 枚のコインを取り除きます。
そして、その次のあかりさんの手番で、あかりさんは最後の 1 枚のコインを取り除きます。
2 回目のちなつさんの手番で、ちなつさんは 1 枚以上のコインを含む山を選ぶことはできません。
従って、あかりさんがゲームに勝利します。
この入力例は部分点の追加制約を満たしています。

入力例 3

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

出力例 3

Chinatsu
Akari
Chinatsu