AT_kupc2018_j ニム?

[problemUrl]: https://atcoder.jp/contests/kupc2018/tasks/kupc2018_j コインの山が $ 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 $ 回それぞれのゲームで、ちなつさんとあかりさんのどちらが勝つかを判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ M $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ b_1 $ $ c_1 $ $ : $ $ b_{M\ -\ 1} $ $ c_{M\ -\ 1} $

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

### 制約 - 入力は全て整数である - $ 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 $ 点が与えられる。 ### Sample Explanation 1 先攻であるちなつさんは最初の手番で、唯一の山の全てのコインを取り除くことができます。 このとき次のあかりさんの手番で、あかりさんはどのような正整数を宣言しても、それ以上の枚数のコインを含む山を選ぶことができません。 従って、ちなつさんがゲームに勝利します。 この入力例は部分点の追加制約を満たしています。 ### Sample Explanation 2 お互い $ 1 $ だけを宣言することができます。 このとき最初のちなつさんの手番で、ちなつさんは山から $ 1 $ 枚のコインを取り除きます。 そして、その次のあかりさんの手番で、あかりさんは最後の $ 1 $ 枚のコインを取り除きます。 $ 2 $ 回目のちなつさんの手番で、ちなつさんは $ 1 $ 枚以上のコインを含む山を選ぶことはできません。 従って、あかりさんがゲームに勝利します。 この入力例は部分点の追加制約を満たしています。