Treasure Hunt

성대한 생일 파티가 끝난 뒤에도 Katie는 Shiro가 좀 더 즐겁게 놀기를 바랐다. 이후 Katie는 보물찾기라는 게임을 생각해 냈다. 물론 가장 친한 친구들인 Kuro and Shiro도 함께 게임을 하자고 초대했다.

세 친구는 매우 영리해서 모든 도전을 아주 빠르게 통과하고 마침내 목적지에 도착했다. 하지만 보물은 고양이 한 마리만 차지할 수 있었기 때문에, 누가 보물을 차지할 자격이 있는지 결정할 방법을 생각하기 시작했다. 곧바로 Kuro가 리본 몇 개를 꺼냈다.

각 고양이에게 무작위의 알록달록한 리본 하나가 주어진다. 리본의 각 색은 대문자 또는 소문자 라틴 문자로 나타낼 수 있다. 리본에 나타나는 연속한 색 부분 수열을 부분 리본이라고 하자. 리본의 아름다움은 그 부분 리본 중 하나가 리본에 나타나는 횟수의 최댓값으로 정의한다. 부분 리본이 더 많이 나타날수록 리본은 더 아름답다. 예를 들어 리본 aaaaaaa는 부분 리본 a가 7번 나타나므로 아름다움이 7이고, 리본 abcdabc는 부분 리본 abc가 두 번 나타나므로 아름다움이 2이다.

규칙은 간단하다. 게임은 n턴 동안 진행된다. 매 턴마다 각 고양이는 자신의 리본에서 정확히 한 위치의 색을 변경 전의 색과 다른 임의의 색으로 바꿔야 한다. 예를 들어 리본 aaab는 한 턴에 acab로 바꿀 수 있다. n턴 후 가장 아름다운 리본을 가진 고양이가 보물을 차지한다.

모두가 최적으로 플레이할 때 누가 승자가 되는지 구한다.

첫째 줄에 턴 수를 나타내는 정수 n가 주어진다 (0 ≤ n ≤ $10^{9}$).

다음 3개 줄에는 Kuro, Shiro and Katie의 리본 3개가 각각 한 줄에 하나씩 주어진다. 각 리본은 최대 $10^{5}$개의 대문자와 소문자 라틴 문자로 이루어진 비어 있지 않은 문자열이다. 공정성을 위해 모든 리본의 길이는 같음이 보장된다. 대문자와 소문자는 서로 다른 색으로 간주한다는 점에 유의한다.

승자의 이름을 출력한다. 가능한 이름은 "Kuro", "Shiro", "Katie"이다. 최대 아름다움을 함께 가진 고양이가 적어도 두 마리라면 "Draw"을 출력한다.

첫 번째 예제에서 Kuro는 3턴 후 자신의 리본을 아름다움이 5인 ooooo로 바꿀 수 있지만, Shiro and Katie가 그러한 아름다움에 도달하는 것은 불가능하다. 둘 다 Shiro and Katie 최대 아름다움 4에는 도달할 수 있는데, 예를 들어 Shiro의 리본을 SSiSS로 바꾸고 Katie의 리본을 Kaaaa로 바꾸면 된다. 따라서 승자는 Kuro이다.

네 번째 예제에서는 각 문자열의 길이가 9이고 턴 수가 15이므로, 모든 고양이는 9턴 후 자신의 문자열을 zzzzzzzzz로 바꾸고, 이어서 문자열을 azzzzzzzz로 바꿨다가 다시 zzzzzzzzz로 바꾸는 일을 세 번 반복함으로써 어떤 방식으로든 자신의 리본을 바꿔 최대 아름다움 9에 도달할 수 있다. 따라서 게임은 무승부로 끝난다.