盛大的生日聚会结束后,凯蒂仍然想让希罗玩得开心。后来,她想出了一个叫寻宝的游戏。当然,她还邀请了她最好的朋友黑和白一起玩。
三个朋友都很聪明,很快就通过了所有的挑战,终于到达了目的地。但宝藏只能属于一只猫,所以他们开始考虑一些可以决定谁值得拥有宝藏的东西。库洛立刻拿出了一些丝带。
每只猫都会收到一条随机的彩色丝带。丝带的每种颜色都可以表示为大写或小写拉丁字母。我们将功能区中出现的连续颜色子序列称为子功能区。丝带的美观度定义为其子丝带之一在丝带中出现的最大次数。子丝带出现的次数越多,丝带就越漂亮。例如,功能区 aaaaaaa 的美度为 $$$7$$$,因为它的子功能区 a 出现了 $$$7$$$ 次,功能区 abcdabc 的美度为 $$$2$$$,因为它的子功能区 abc 出现了两次。
规则很简单。游戏将有 $$$n$$$ 回合。每回合,每只猫都必须严格将其丝带中的一种颜色(在一个位置)更改为与未更改的颜色不同的任意颜色。例如,功能区 aaab 可以转一圈变为 acab。经过 $$$n$$$ 轮后,拥有最美丽丝带的人将赢得宝藏。
如果他们都发挥最佳,你能找出谁将成为获胜者吗?
输入
第一行包含一个整数 $$$n$$$ ($$$0 \leq n \leq 10^{9}$$$) — 匝数。
接下来 3 行包含 Kuro、Shiro 和 Katie 的 3 条丝带,每行各一条。每个功能区都是一个字符串,其中包含不超过 $$$10^{5}$$$ 大写和小写拉丁字母,并且不为空。保证所有丝带的长度相等,以保证公平。请注意,大写和小写字母被视为不同的颜色。
输出
打印获胜者的姓名(“Kuro”、“Shiro”或“Katie”)。如果至少有两只猫拥有最大的美丽,则打印“Draw”。
示例
输入 #1
3 Kuroo Shiro Katie
输出 #1
Kuro
输入 #2
7 treasurehunt threefriends hiCodeforces
输出 #2
Shiro
输入 #3
1 abcabc cbabac ababca
输出 #3
Katie
输入#4
15 foPaErcvJ mZaxowpbt mkuOlaHRE
输出#4
Draw
注意
第一个例子中,在$$$3$$$转弯后,Kuro可以将自己的丝带变成ooooo,具有$$$5$$$的美感,而Shiro和Katie则不可能达到这样的美感(Shiro和Katie最多只能达到$$$4$$$的美感,例如将Shiro的丝带改为SSiSS,将Katie的丝带改为Kaaaa)。因此,获胜者是Kuro。
在第四个例子中,由于每根绳子的长度为$$$9$$$,圈数为$$$15$$$,因此每个人都可以通过某种方式改变自己的丝带,以达到$$$9$$$的最大美感,即在9圈后将其绳子变为zzzzzzzzzz,并重复将其绳子变为azzzzzzzz,然后变为zzzzzzzzzz三次。因此,比赛以平局结束。