B. Охота за сокровищами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После празднования дня рождения Кэти решила, что Широ надо ещё повеселиться. Поэтому она придумала игу про охоту за сокровищами и пригласила её лучших подруг Куро и Широ поиграть вместе с ней.

Поскольку подруги достаточно умны, они быстро прошли все испытания и достигли цели. Но, к сожалению, сокровище достанется только одной из них, поэтому им необходимо было придумать метод, как выявить среди них победителя. Для этого Куро придумала метод с цветными лентами.

Каждой из трёх подруг даётся по случайной многоцветной ленте. Каждый цвет на ленте обозначается большой или маленькой буквой английского алфавита. Назовём непрерывный подотрезок цветов, встречающийся на ленте, подлентой. Красота ленты будет определяться как максимальное количество раз, которое одна из его подлент встречается в ленте. Чем чаще встречается подлента, тем красивее лента. Например, красота ленты aaaaaaa равна $$$7$$$, так как подлента a встречается в ней $$$7$$$ раз, а красота ленты abcdabc равна $$$2$$$, поскольку подлента abc встречается в ней дважды.

Правила просты: в игре будет $$$n$$$ ходов. Каждый ход каждая из подруг обязана поменять ровно один участок цвета в её ленте на любой другой цвет, выбранный ей. Например, ленту aaab можно за один ход поменять на acab. Сокровища получает та, чья лента после $$$n$$$ ходов будет наиболее красивой.

Можете ли вы определить, кто победит при наилучшей возможной игре каждого игрока?

Входные данные

В первой строке содержится целое число $$$n$$$ ($$$0 \leq n \leq 10^{9}$$$) — количество ходов.

В следующих 3 строках содержатся 3 ленты Куро, Широ и Кэти, каждая в отдельной строке, соответственно. Каждая лента — непустая строка, содержащая не более $$$10^{5}$$$ прописных и строчных (маленьких и больших) букв английского алфавита. Гарантируется, что длины всех лент равны для честности состязания. Обратите внимание, что прописные и строчные буквы обозначают разные цвета.

Выходные данные

Выведите имя победителя на латинице — «Kuro», «Shiro» или «Katie». Если после окончания игры максимальное значение красоты будет хотя бы у двух лент, выведите «Draw».

Примеры
Входные данные
3
Kuroo
Shiro
Katie
Выходные данные
Kuro
Входные данные
7
treasurehunt
threefriends
hiCodeforces
Выходные данные
Shiro
Входные данные
1
abcabc
cbabac
ababca
Выходные данные
Katie
Входные данные
15
foPaErcvJ
mZaxowpbt
mkuOlaHRE
Выходные данные
Draw
Примечание

В первом примере после $$$3$$$ ходов Куро может преобразовать свою ленту в ooooo, имеющую красоту $$$5$$$, в то время как достижение такой красоты невозможно для Кэти и Широ (и Широ, и Кэти могут максимум достичь красоты $$$4$$$, например, превратив ленту Широ в SSiSS и превратив ленту Кэти в Kaaaa). Поэтому победит Куро.

В четвёртом примере, так как длина каждой строки равна $$$9$$$, а количество ходов равно $$$15$$$, все могут превратить свои ленты таким путём, чтобы достичь максимальной красоты $$$9$$$, например, превратив свои строки в zzzzzzzzz после 9 ходов, и поочерёдно превращая свои строки в azzzzzzzz, а потом обратно в zzzzzzzzz, трижды. Поэтому игра закончится ничьёй.