Charlie Brown adora brincar com os seus amigos. Ultimamente, sempre que pretende jogar futebol, torna-se complicado decidir quem vai para guarda-redes, pois ninguém quer essa posição. Sendo assim, ficou decidido que se usa o "um-dó-li-tá" para tomar essa decisão. Sabes como funciona?
Primeiro, os amigos juntam-se num círculo. Neste último jogo, eram 4:
Charlie Snoopy Linus Lucy
Depois, começam a contar num deles e seguem a frase "um dó li tá quem está livre livre está", que tem 9 palavras. Para cada uma das palavras vai-se apontando para uma pessoa e seguindo no sentido dos ponteiros do relógio:
Charlie | Linus | Lucy | Snoopy -------------------------------------- 1 um | 2 dó | 3 li | 4 tá 5 quem | 6 está | 7 livre | 8 livre 9 está |
E neste caso o Charlie Brown fica livre e sai da roda, ficando os outros 3. Segue-se na pessoa seguinte (neste caso o Linus) e a frase começa de novo e quem se livra a seguir é o Snoopy. Continuando da mesma forma livra-se o Linus e sobra a Lucy, que tem de ir para guarda-redes.
Sabendo onde se começa a contar, Charlie Brown gostava muito de saber em que lugar se colocar na roda para não ter de ir à baliza. O problema é que a frase usada nem sempre é a mesma. Será que podes ajudá-lo ?
Na primeira linha de input vem um número inteiro C, indicando o número de casos a considerar (1≤C≤5).
Seguem-se exactamente C*2 linhas, cada uma contendo a descrição de um caso. A primeira linha de cada caso indica quais os amigos presentes na roda, dados por ordem dos ponteiros do relógio (nota que a seguir ao último menino vem novamente o primeiro). A contagem começa sempre no primeiro menino desta linha. Segue-se uma outra linha contendo a frase a usar.
Todos os nomes dos meninos e das palavras a usar são constituídos unicamente por números e letras maíusculas ou mínusculas (sem acentos), estando delimitados por espaços e/ou mudanças de linha. Quer os nomes quer as palavras têm no máximo 10 letras. Quer o número de meninos, quer o número de palavras da frase, serão sempre superiores ou iguais a 1 e inferiores ou iguais a 100000.
O output é constituído por C linhas, uma para cada caso dado (pela mesma ordem em que vinham no input). Cada uma dessas linhas deve conter um único nome, indicando qual o menino escolhido para guarda-redes, segundo o processo descrito.
2 Charlie Linus Lucy Snoopy um do li ta quem esta livre livre esta Charlie Snoopy Lucy pim pam pum
Lucy Snoopy