配点 : 400 点
問題文
一堆硬币 有 N 件。
在山里 它们的编号最大为 1 到 N ,i 第一座山是 由 a_i 硬币组成。
使用这些硬币堆来创建以下内容 2 考虑一下人类游戏。
- 玩家分为先玩者和后玩者。
- 从第一个玩家开始,每个玩家轮流进行。轮到你时,执行以下操作 2 按顺序执行两个操作。
小于或等于
- K 的正整数
声明 x 。
然而,彼此 2 在随后的回合中,该数字小于上一回合中声明的整数。 请勿声明 x 。 一堆至少包含 - x 枚硬币 1 选择一个并从硬币堆中取出一枚硬币。 x 删除。
如果不存在这样的山,游戏就在那里结束,另一位玩家赢得游戏。
- K 的正整数
声明 x 。
Chinatsu-san 和 Akari-san 玩这个游戏,Chinatsu-san 玩第一,Akari-san 玩第二。 我决定重复 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(第二位玩家)获胜
输出 Akari 。
入力例 1
1 8 1 7
出力例 1
Chinatsu
先走的千夏可以在第一回合从唯一的一堆硬币中取出所有硬币。
此时,在 Akari 的下一个回合中,无论她声明什么正整数,她都无法选择包含更多硬币的一堆。
因此,千夏赢得了比赛。
该输入示例满足部分点相加约束。
入力例 2
1 1 1 2
出力例 2
Akari
彼此
只能声明 1 。
这时,在千夏第一个转弯时,千夏从山上移动了。
取出 1 硬币。
然后,在明里的下一个回合,明里 1 硬币。
2 轮到千夏了,千夏
您无法选择包含超过 1 枚硬币的一堆。
因此,Akari 赢得了比赛。
该输入示例满足部分点相加约束。
入力例 3
5 7 3 83795 19140 82706 34385 26675 2 74621 3 60951
出力例 3
Chinatsu Akari Chinatsu