После празднования дня рождения Кэти решила, что Широ надо ещё повеселиться. Поэтому она придумала игу про охоту за сокровищами и пригласила её лучших подруг Куро и Широ поиграть вместе с ней.
Поскольку подруги достаточно умны, они быстро прошли все испытания и достигли цели. Но, к сожалению, сокровище достанется только одной из них, поэтому им необходимо было придумать метод, как выявить среди них победителя. Для этого Куро придумала метод с цветными лентами.
Каждой из трёх подруг даётся по случайной многоцветной ленте. Каждый цвет на ленте обозначается большой или маленькой буквой английского алфавита. Назовём непрерывный подотрезок цветов, встречающийся на ленте, подлентой. Красота ленты будет определяться как максимальное количество раз, которое одна из его подлент встречается в ленте. Чем чаще встречается подлента, тем красивее лента. Например, красота ленты aaaaaaa равна \(7\), так как подлента a встречается в ней \(7\) раз, а красота ленты abcdabc равна \(2\), поскольку подлента abc встречается в ней дважды.
Правила просты: в игре будет \(n\) ходов. Каждый ход каждая из подруг обязана поменять ровно один участок цвета в её ленте на любой другой цвет, выбранный ей. Например, ленту aaab можно за один ход поменять на acab. Сокровища получает та, чья лента после \(n\) ходов будет наиболее красивой.
Можете ли вы определить, кто победит при наилучшей возможной игре каждого игрока?
Выходные данные
Выведите имя победителя на латинице — «Kuro», «Shiro» или «Katie». Если после окончания игры максимальное значение красоты будет хотя бы у двух лент, выведите «Draw».
Примечание
В первом примере после \(3\) ходов Куро может преобразовать свою ленту в ooooo, имеющую красоту \(5\), в то время как достижение такой красоты невозможно для Кэти и Широ (и Широ, и Кэти могут максимум достичь красоты \(4\), например, превратив ленту Широ в SSiSS и превратив ленту Кэти в Kaaaa). Поэтому победит Куро.
В четвёртом примере, так как длина каждой строки равна \(9\), а количество ходов равно \(15\), все могут превратить свои ленты таким путём, чтобы достичь максимальной красоты \(9\), например, превратив свои строки в zzzzzzzzz после 9 ходов, и поочерёдно превращая свои строки в azzzzzzzz, а потом обратно в zzzzzzzzz, трижды. Поэтому игра закончится ничьёй.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
Kuroo
Shiro
Katie
|
Kuro
|
|
2
|
7
treasurehunt
threefriends
hiCodeforces
|
Shiro
|
|
3
|
1
abcabc
cbabac
ababca
|
Katie
|
|
4
|
15
foPaErcvJ
mZaxowpbt
mkuOlaHRE
|
Draw
|