Problem
Des concours de programmation ont lieu chaque année à Saint-Pétersbourg, à Barnaoul et dans certaines villes de l'étranger proche. Ces compétitions se déroulent dans le cadre du championnat du monde étudiant en programmation, organisé par l'une des associations les plus respectées ACM (Association for Computing Machinery). Lors de ces compétitions, des équipes de la région d'Europe du Nord-Est NEERC (North-Eastern European Regional Contest) sont sélectionnées. Chaque année, les organisateurs de la compétition sont confrontés au problème de déterminer les équipes qui seront invitées à participer à la finale du Championnat du monde de programmation. Selon les nouvelles règles, pas plus de N équipes représentant le NEERC vont à la finale. De plus, plus de k équipes ne peuvent pas passer d'une université. Dans le même temps, parmi tous ces ensembles, celui dans lequel la somme des places occupées par ces équipes dans les compétitions des demi-finales est le minimum possible est sélectionné. Votre tâche consiste à déterminer quelles équipes seront invitées à participer à la finale de la Coupe du monde sur la base du protocole final des compétitions de demi-finale et des numéros N et k.
Entrée
Dans la première ligne du fichier d'entrée, il y a trois nombres naturels Р (1 ≤ P ≤ 100000) — le nombre d'équipes participant à la demi-finale, N (1≤ N ≤ P ) et k (1≤ k ≤ P ) . Les lignes P suivantes, une par ligne, listent les noms des universités dont les équipes ont pris les places correspondantes. Le nom de l'université contient des lettres latines minuscules et majuscules et des espaces. La longueur du nom de l'université ne dépasse pas 30 caractères. La ligne suivante répertorie les numéros d'équipe des universités respectives. Ainsi, si le nom de l'université est écrit dans la i -ème ligne (2 ≤ i ≤ P + 1) , alors cette équipe a pris i - 1 place en demi-finale et a un numéro écrit en i - 1 place en P + 2 ligne.
Sortie
Dans le fichier de sortie, imprimez les noms des équipes invitées à participer à la finale du Championnat du monde de programmation, triées par place occupée en demi-finale. Comme nom d'équipe, écrivez le nom de l'université suivi d'un espace #le numéro de l'équipe.
Exemple
| # |
Entrée |
Sortie |
| 1 |
9 5 2
Université fantastique
Université folle
Université fantastique
Université fantastique
Très bien
Bon toi
Très bien
Université folle
Bon toi
1 1 2 3 2 1 1 2 2
Université fantastique #1
Université folle #1
Université fantastique #2
Très bien U #2
Bon U #1