물단지 게임

프로그래밍 대회 당일 일정은 보통 비슷한 흐름을 따른다. 아침에 워밍업을 하고, 점심시간과 휴식시간을 보낸 뒤, 대회 환경을 마지막으로 점검하고 나서 대회가 시작된다.

휴식시간에 어떤 참가자는 쉬는 것을 좋아하고, 어떤 참가자는 어울려 노는 것을 좋아하며, 또 어떤 참가자는 카드 게임을 하는 습관이 있다. Luciano와 그의 친구들은 "물단지(Jar of Water)"라는 게임을 즐긴다. 매번 우승하지 못하는 데 지친 Luciano는 모든 플레이어의 초기 카드가 주어졌을 때(그가 어떻게 아는지는 묻지 말자) 자신이 이길지 여부를 판단하는 프로그램을 작성하려 한다. 만약 그가 이기지 못할 것이라면, 아무 핑계를 대고 그 판에 참여하지 않겠다고 말할 수 있다.

게임은 다음과 같이 진행된다.

• 사용하는 덱에는 "A23456789DQJK"(이 순서대로 값이 낮은 것에서 높은 것) 카드가 들어 있으며, 무늬는 무시한다. 여기에 조커 카드 하나가 더 있다.
• N명의 참가자가 원을 이루며 나란히 앉는다. 참가자 1은 참가자 2의 바로 왼쪽에, 참가자 2는 참가자 3의 바로 왼쪽에 있고, 이런 식으로 원을 이루어 참가자 N이 참가자 1의 바로 왼쪽에 오게 된다. 참가자 K가 무작위로 선택되어 게임을 시작한다.
• N명의 참가자가 있는 게임에는 N가지 값 각각의 카드가 네 장씩 있고 조커가 한 장 있다. 게임 시작 시 참가자 K가 조커를 받는다. 나머지 카드는 섞여서 각 플레이어가 네 장씩 받도록 분배된다.
• 매 라운드에서 순서가 된 참가자는 자신의 카드 중 하나를 골라 오른쪽 참가자에게 넘긴다. 카드를 받은 참가자가 다음 순서가 된다.
• 참가자가 정확히 네 장의 카드를 들고 있고 그것들이 모두 같은 값이면 그 참가자는 승리 상태에 있다고 한다. 게임은 적어도 한 명의 참가자가 승리 상태에 있게 되는 즉시 끝난다. 이때 승리 상태에 있는 참가자 중 번호가 가장 작은 참가자가 게임의 우승자로 선언된다.

한 참가자에서 다음 참가자로 넘길 카드는 다음 규칙으로 선택된다.

• 조커는 받은 직후 바로 넘길 수 없다. 이는 첫 라운드 직전에 카드 분배자로부터 조커를 받은 시작 플레이어에게도 적용된다.
• 참가자는 가능하면 항상 조커를 다음 사람에게 넘긴다.
• 참가자가 조커를 넘길 수 없으면, 참가자는 자신의 패에서 가장 적게 나오는 카드를 골라 다음 참가자에게 넘긴다. 가장 적게 나오는 카드가 여러 장이면, 그중에서 위에 나온 순서대로 값이 가장 낮은 카드를 고른다.

규칙을 파악했으니, Luciano를 도와 게임의 초기 상태가 주어졌을 때 어떤 플레이어가 우승자로 선언될지 알려주는 프로그램을 작성하자.

첫째 줄에 두 정수 N과 K(2 ≤ N ≤ 13, 1 ≤ K ≤ N)가 주어진다. 이는 게임에 참여하는 참가자의 수와 게임을 시작하는 참가자를 각각 나타낸다. 다음 N개 줄에는 각각 네 문자가 주어지며, 이는 i번째 참가자의 초기 카드(조커는 제외)를 나타낸다.

프로그램은 게임의 우승자로 선언되는 참가자의 번호를 나타내는 정수 하나를 한 줄에 출력해야 한다.