Participant List

Interview

Time limit1sMemory limit512 MB

Summary

Keep the first M applicants per class, then print Blue (odd) classes before White (even), each class sorted by name length, then alphabetically.

Level: Easy3 of 10
Topics: Implementation, Sorting
Solved: No attempts yet

문제

Baeknam's alma mater, a high school, is hosting a sports day.

Baeknam manages the student applications for the sports day.

Only classes 1 through $N$ take part, and each class can enroll up to $M$ students on a first-come, first-served basis. $N$ is even.

The teams are split by class number. Odd-numbered classes form the Blue team, and even-numbered classes form the White team.

Baeknam is writing a program that prints the participant list. The program must follow these rules:

Print the Blue team first, then the White team.
For each team, print the classes in ascending order.
For each class, print the student names by length, shortest first. Names of equal length are sorted alphabetically.

입력

The first line contains $N$ , the number of classes, and $M$ , the number of students each class can enroll. $N$ is even, $2 \le N \le 10$ , and $1 \le M \le 10$ .

From the second line on, each line gives a student's class and name in the order they applied. The class does not exceed $N$ . Names use only lowercase letters and are at most 15 characters long.

No two students have the same class and name.

The maximum number of applicants is 500.

The input ends with 0 0.

출력

Starting from the first line, print each student's class and name separated by a space, following the program's order.

Examples1

Example 1

Input

4 2
3 sunyoung
2 junkyu
2 dohyun
1 minjun
3 kihyun
2 damin
4 hyunsu
0 0

Expected output

1 minjun
3 kihyun
3 sunyoung
2 dohyun
2 junkyu
4 hyunsu