B. Treasure Hunt

Codeforces

IDCF979B

Time1000ms

Memory256MB

Difficulty—

greedy

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 \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. ## 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_". [samples] ## 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.

Samples

Input #1

3
Kuroo
Shiro
Katie

Output #1

Kuro

Input #2

7
treasurehunt
threefriends
hiCodeforces

Output #2

Shiro

Input #3

1
abcabc
cbabac
ababca

Output #3

Katie

Input #4

15
foPaErcvJ
mZaxowpbt
mkuOlaHRE

Output #4

Draw

API Response (JSON)

{
  "problem": {
    "name": "B. Treasure Hunt",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF979B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments