beecrowd | 2971

Jogo de Baralho

Por Maratona SBC de Programação BR Brazil

Timelimit: 1

O cronograma do dia das competições de programação normalmente segue o mesmo padrão: aquecimento de manhã, seguido do horário de almoço, um tempo de descanso, ajustes finais do ambiente de competição e então o início da prova.

No tempo de descanso, alguns competidores preferem relaxar, outros preferem socializar e uma parte tem o costume de jogar algum jogo de baralho. Luciano e seus amigos gostam de jogar um jogo conhecido como "Copo d'água". Cansado de não ser o vencedor, Luciano quer escrever um programa que, dadas as cartas iniciais de todos os jogadores (não me pergunte como ele sabe disso), determine se ele irá vencer ou não. Se ele não for vencer, ele pode então inventar uma desculpa qualquer e pedir para não participar daquela rodada.

O jogo funciona da seguinte maneira:

– O baralho utilizado possui as cartas: "A23456789DQJK" (nessa ordem, de menor para maior valor), onde os naipes são ignorados. Além disso, o baralho possui mais uma única carta extra: o curinga.

N competidores sentam lado a lado em círculo. O competidor 1 está imediatamente àa esquerda do 2, que está imediatamente àa esquerda do 3, e assim por diante até completar o círculo com o N-ésimo competidor imediatamente àa esquerda do 1. Um competidor K é sorteado para iniciar o jogo.

– Em um jogo com N competidores, existirão quatro cartas de N diferentes valores e um curinga. No começo do jogo, o competidor K recebe o curinga; as demais cartas são embaralhadas e distribuídas entre os jogadores, de modo que cada jogador receba quatro delas.

– Em cada rodada, o jogador da vez escolhe uma de suas cartas e a passa para o jogador à sua direita. O jogador que recebeu uma carta será o próximo jogador da vez.

– Dizemos que um jogador está em estado vencedor se possuir exatamente quatro cartas em mãos e elas forem todas iguais. O jogo termina assim que ao menos um competidor estiver em estado vencedor. Nesse caso, o competidor de menor índice em estado vencedor será declarado o jogador vencedor.

A carta que será passada de um competidor para o próximo é definida pela seguinte regra:

– O curinga nunca pode ser passado logo depois de ser recebido. Isso também se aplica ao jogador inicial, que recebeu o curinga do distribuidor de cartas logo antes da primeira rodada.

– O competidor irá, sempre que possível, passar o curinga para o próximo.

– Caso não passe o curinga, o competidor irá escolher a carta que menos aparece em sua mão e passar para o próximo. Caso exista mais de uma carta que aparece uma menor quantidade de vezes, ele irá passar, dentre essas, a carta de menor valor de acordo com a ordem descrita anteriormente.

Sabendo das regras, ajude Luciano escrevendo um programa que, dada a configuração inicial do jogo, diga qual jogador será declarado vencedor.

Entrada

A primeira linha contém dois inteiros N e K (2 <= N <= 13 e 1 <= K <= N) representando, respectivamente, a quantidade de competidores e o competidor que iniciará o jogo. Cada uma das próximas N linhas conterá quatro caracteres, representando as cartas iniciais do i-ésimo competidor (com exceção do curinga).

Saída

Seu programa deve produzir uma única linha com um inteiro representando o competidor que será declarado vencedor.

Exemplos de Entrada Exemplos de Saída

2 1

33J3

JJJ3

2

2 2

A2A2

22AA

2

4 2

774Q

JJQ7

44Q7

4QJJ

3