Treasure Hunt

题意翻译

在一场盛大的生日派对后，Katie（以下简称Ka）仍然想和Shiro(以下简称S）去找更多的乐子。不一会，她就想到了一个游戏，叫做寻宝。当然，她邀请了她最好的朋友Kuro（以下简称Ku）和S和她一起玩。 三个朋友都很聪明所以他们很快的通过了所有挑战并且终于到达了终点。但是宝藏只能属于一只猫（主角们都是猫），所以他们开始想个决定宝藏归属的法子。很快的，Ku带着一些丝带前来。 每只猫都被发放了一条随机颜色，鲜艳的丝带。每一种丝带的颜色都可以用大写字母或小写字母表示。我们定义：一种颜色的字母表达式内的一段连续子序列既是丝带中的一段子丝带。丝带美丽的程度由它的子丝带出现次数的最大值决定。越多子丝带，这条丝带就越美丽，比如说，aaaaaaa色的丝带有美丽值7，因为它的子序列出现了7次，abcdabc有美丽值2，因为它的子序列abc出现了两次。 规则很简单。游戏将会进行n轮，每一轮每一只猫都必须对自己的丝带改变严格的“一种”颜色（在自己的回合），使之变成不同于之前的随机颜色。比如说,aaab可以在一回合内变成acab。n轮游戏后美丽值最大的丝带的主人赢得比赛。 输入： 第一行包含一个整数n,代表回合数。 接下来的三行包含Ku,S，Ka的三条丝带，一条丝带各自占一行。每一条丝带都是一个字符串，包含不超过1e5的大小写字母组合而且不是空字符串。为了公平，保证三条丝带长度相同。注意大小写字母被认为表示了不同的颜色。 输出： 输出赢家的名字 ("Kuro", "Shiro" 或是 "Katie")，如果至少两只猫的丝带有相同的美丽值，那么输出“Draw（平局）”。

题目描述

After the big birthday party, Katie still wanted Shiro to have some more fun. Later, she came up with a game called treasure hunt. Of course, she invited her best friends Kuro and Shiro to play with her. The three friends are very smart so they passed all the challenges very quickly and finally reached the destination. But the treasure can only belong to one cat so they started to think of something which can determine who is worthy of the treasure. Instantly, Kuro came up with some ribbons. A random colorful ribbon is given to each of the cats. Each color of the ribbon can be represented as an uppercase or lowercase Latin letter. Let's call a consecutive subsequence of colors that appears in the ribbon a subribbon. The beauty of a ribbon is defined as the maximum number of times one of its subribbon appears in the ribbon. The more the subribbon appears, the more beautiful is the ribbon. For example, the ribbon aaaaaaa has the beauty of $ 7 $ because its subribbon a appears $ 7 $ times, and the ribbon abcdabc has the beauty of $ 2 $ because its subribbon abc appears twice. The rules are simple. The game will have $ n $ turns. Every turn, each of the cats must change strictly one color (at one position) in his/her ribbon to an arbitrary color which is different from the unchanged one. For example, a ribbon aaab can be changed into acab in one turn. The one having the most beautiful ribbon after $ n $ turns wins the treasure. Could you find out who is going to be the winner if they all play optimally?

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 0 \leq n \leq 10^{9} $ ) — the number of turns. Next 3 lines contain 3 ribbons of Kuro, Shiro and Katie one per line, respectively. Each ribbon is a string which contains no more than $ 10^{5} $ uppercase and lowercase Latin letters and is not empty. It is guaranteed that the length of all ribbons are equal for the purpose of fairness. Note that uppercase and lowercase letters are considered different colors.

输出格式

Print the name of the winner ("Kuro", "Shiro" or "Katie"). If there are at least two cats that share the maximum beauty, print "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

说明

In the first example, after $ 3 $ turns, Kuro can change his ribbon into ooooo, which has the beauty of $ 5 $ , while reaching such beauty for Shiro and Katie is impossible (both Shiro and Katie can reach the beauty of at most $ 4 $ , for example by changing Shiro's ribbon into SSiSS and changing Katie's ribbon into Kaaaa). Therefore, the winner is Kuro. In the fourth example, since the length of each of the string is $ 9 $ and the number of turn is $ 15 $ , everyone can change their ribbons in some way to reach the maximal beauty of $ 9 $ by changing their strings into zzzzzzzzz after 9 turns, and repeatedly change their strings into azzzzzzzz and then into zzzzzzzzz thrice. Therefore, the game ends in a draw.

题意翻译

在一场盛大的生日派对后，Katie（以下简称Ka）仍然想和Shiro(以下简称S）去找更多的乐子。不一会，她就想到了一个游戏，叫做寻宝。当然，她邀请了她最好的朋友Kuro（以下简称Ku）和S和她一起玩。 三个朋友都很聪明所以他们很快的通过了所有挑战并且终于到达了终点。但是宝藏只能属于一只猫（主角们都是猫），所以他们开始想个决定宝藏归属的法子。很快的，Ku带着一些丝带前来。 每只猫都被发放了一条随机颜色，鲜艳的丝带。每一种丝带的颜色都可以用大写字母或小写字母表示。我们定义：一种颜色的字母表达式内的一段连续子序列既是丝带中的一段子丝带。丝带美丽的程度由它的子丝带出现次数的最大值决定。越多子丝带，这条丝带就越美丽，比如说，aaaaaaa色的丝带有美丽值7，因为它的子序列出现了7次，abcdabc有美丽值2，因为它的子序列abc出现了两次。 规则很简单。游戏将会进行n轮，每一轮每一只猫都必须对自己的丝带改变严格的“一种”颜色（在自己的回合），使之变成不同于之前的随机颜色。比如说,aaab可以在一回合内变成acab。n轮游戏后美丽值最大的丝带的主人赢得比赛。 输入： 第一行包含一个整数n,代表回合数。 接下来的三行包含Ku,S，Ka的三条丝带，一条丝带各自占一行。每一条丝带都是一个字符串，包含不超过1e5的大小写字母组合而且不是空字符串。为了公平，保证三条丝带长度相同。注意大小写字母被认为表示了不同的颜色。 输出： 输出赢家的名字 ("Kuro", "Shiro" 或是 "Katie")，如果至少两只猫的丝带有相同的美丽值，那么输出“Draw（平局）”。