Problem
As competições de programação são realizadas anualmente em São Petersburgo, Barnaul e algumas cidades do exterior próximo. Estas competições fazem parte do campeonato mundial estudantil de programação, organizado por uma das mais respeitadas associações ACM (Association for Computing Machinery). Nestas competições, são selecionadas equipas da Região do Nordeste Europeu NEERC (Competição Regional do Nordeste Europeu). Todos os anos, os organizadores da competição enfrentam o problema de definir as equipes que serão convidadas a participar das finais do Campeonato Mundial de Programação. De acordo com as novas regras, não mais do que N equipes representando o NEERC vão para a final. Além disso, mais de k equipes não podem passar de uma universidade. Ao mesmo tempo, de todos esses conjuntos, é selecionado aquele em que a soma das vagas ocupadas por essas equipes nas competições semifinais é a mínima possível. Sua tarefa é determinar quais equipes serão convidadas a participar da final da Copa do Mundo com base no protocolo final das competições semifinais e nos números N e k.
Entrada
Na primeira linha do arquivo de entrada existem três números naturais Р (1 ≤ P ≤ 100000) — o número de times participantes da semifinal, N (1 ≤ N ≤ P ) e k (1 ≤ k ≤ P ) . As próximas P linhas, uma por linha, listam os nomes das universidades cujas equipes ocuparam as vagas correspondentes. O nome da universidade contém letras latinas minúsculas e maiúsculas e espaços. O comprimento do nome da universidade não excede 30 caracteres. A próxima linha lista os números das equipes das respectivas universidades. Assim, se o nome da universidade estiver escrito na i -ésima linha (2 ≤ i ≤ P + 1) , então esta equipe conquistou i - 1 lugar nas semifinais e tem um número escrito em i - 1 lugar na linha P + 2.
Saída
No arquivo de saída imprima os nomes das equipes convidadas a participar das finais do Campeonato Mundial de Programação, ordenadas pela vaga ocupada nas semifinais. Como nome da equipe, imprima o nome da universidade seguido de um espaço #o número da equipe.
Exemplo
| # |
Entrada |
Saída |
| 1 |
9 5 2
Universidade da Fantasia
Universidade Maluca
Universidade da Fantasia
Universidade da Fantasia
Muito bom U
Bom U
Muito bom U
Universidade Maluca
Bom U
1 1 2 3 2 1 1 2 2
|
Universidade da Fantasia #1
Universidade Maluca #1
Universidade da Fantasia #2
Muito Bom U #2
Bom U #1
|