J - ニム?

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

コインの山が 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 点が与えられる。


入力

入力は以下の形式で標準入力から与えられる。

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

出力

i 行目には、i 回目のゲームでちなつさん (先攻) が勝つならば Chinatsu を、あかりさん (後攻) が勝つならば Akari を出力せよ。


入力例 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