Treasure Hunt CodeForces - 979B （思维+map）

B. Treasure Hunt

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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?

Input

The first line contains an integer $n$ ($0\le n\le {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.

Output

Print the name of the winner ("Kuro", "Shiro" or "Katie"). If there are at least two cats that share the maximum beauty, print "Draw".

Examples

input

Copy

3
Kuroo
Shiro
Katie

output

Copy

Kuro

input

Copy

7
treasurehunt
threefriends
hiCodeforces

output

Copy

Shiro

input

Copy

1
abcabc
cbabac
ababca

output

Copy

Katie

input

Copy

15
foPaErcvJ
mZaxowpbt
mkuOlaHRE

output

Copy

Draw

Note

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.

题意：三个人在玩游戏，给出三个等长的字符串，然后进行n次操作，每次操作必须改变字符串的一个字母。这三个人都是足够聪明的，求最后谁的字符串相同的子串最多！最多的不止一个，那么输出“Draw”，否则，输出名字

思路：可以知道，要想子串最多，那么一定是全变成同一个字母！如果一个字符串没有全部相通的话，那么，每一次操作，必定能使他相同的子串加1！ 知道了这些以后，就很好办了，只需记录一下字符串种重复次数最多的一个字母的个数MAX，然后让MAX与n相加，如果小于或等于len即字符串的长度，就是MAX+n。否则就是len，但是，有一种特殊的情况就是如果字符串的最大相同子串的个数已经等于len，并且n=1的时候，那么这个最大相同子串等于len-1.  其他情况都可以通过多次变换而变回原来的值，例如，如果最大相同子串的长是len即   aaaaaaa的情况，如果n=1，必定会减一，而如果n！=1，那么都可以将一个a经过n-1次的其他变换，最后在第n次变回a。

#include "iostream"
#include "cstring"
#include "algorithm"
#include "cmath"
#include "map"
using namespace std;
char str[5][100005];
struct P
{
    int MAX,man;
};
P s[5];
map<char,int> mp;
bool cmp(P a,P b)
{
    return a.MAX>b.MAX;
};
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<3;i++){
        cin>>str[i];
        s[i].MAX=0;
        s[i].man=i+1;
    }
    int len=strlen(str[0]);
    for(int i=0;i<3;i++){
        mp.clear();
        for(int j=0;j<len;j++){
            mp[str[i][j]]++;
            s[i].MAX=max(mp[str[i][j]],s[i].MAX);
        }
        if(s[i].MAX+n>len){
            if(n!=1)
                s[i].MAX=len;
            else
                s[i].MAX=len-1;
        }
        else
            s[i].MAX+=n;
    }
    sort(s,s+3,cmp);
    if(s[0].MAX==s[1].MAX)
        cout<<"Draw"<<endl;
    else{
        if(s[0].man==1)
            cout<<"Kuro"<<endl;
        else if(s[0].man==2)
            cout<<"Shiro"<<endl;
        else
            cout<<"Katie"<<endl;
    }
    return 0;
}