#D0333. 假痴不癫

假痴不癫

题目背景

宁伪作不知不为,不伪作假知妄为。静不露机,云雷屯也。

题目描述

33DAI 对博弈论非常在行,所以 Kitten 总是不愿意陪他玩。通过多日的装疯卖傻,33DAI 终于麻痹了 Kitten,他们开始玩取石子游戏。

初始有 nn 个石子,两个人轮流开始取石子操作,33DAI 先开始操作。

  • 如果某人操作时面临的石子数量满足“当前石子数量是一个质数或者小于 22”,则游戏结束且这人获胜。
  • 如果当前游戏不会结束,则可以从中去掉 xx 个石子(要求 1xk1\le x\le kxx 必须小于等于当前石子数量)。

假设两个人都希望自己获胜,且都足够聪明。求最后谁会获胜。

输入格式

一行两个整数 n,kn,k

输出格式

如果 33DAI 会获胜,输出 33DAI,否则输出 Kitten

13 10
33DAI

33DAI 一来就是个必胜状态,真好。

28 1
Kitten

每次只能取走一个石子,游戏发展过程为:28(33DAI),27(Kitten),26(33DAI),25(Kitten),24(33DAI),23(Kitten)

6 2
33DAI

33DAI 会取走两个石子,把石子数变为 44,加下来 Kitten 不管怎么操作,都会给 33DAI 一个获胜的局面。

10 5
Kitten

33DAI 如果把石子数变成 7,57,5Kitten 赢了,如果把石子变成 6,8,96,8,9 则 Kitten 可以把石子数变为 44,然后 33DAI 操作 44 后,还是会给 Kitten 一个获胜的状态。

数据规模与约定

对于 100%100\% 的数据,1n50001 \le n\le 50001k101\le k\le 10

  • 子任务 1(10 分):保证 nn 是个质数。
  • 子任务 2(20 分):保证 k=1k=1
  • 子任务 3(30 分):保证 k=2k=2
  • 子任务 4(40 分):没有特殊限制。