eolymp
bolt
Try our new interface for solving problems

ICQ

Time limit 0.5 seconds
Memory limit 64 MiB

In some schools, each student has a personal number ICQ. The school is widely believed that the smaller the value of numbers ICQ, the more advanced a schoolboy. Known list of all students, with numbers ICQ. K is required to display the list of the most advanced students.

Input data

In the first line of input contains the number of pupils in the school N (1 ≤ N ≤ 100) and the number of K (1 ≤ K ≤ N). This is followed by N lines, each line contains the name of the student (with no spaces, contains no more than 20 lower-case Latin letters) and through the gap number ICQ (1 ≤ ICQ ≤ 10^9). ICQ number and names of students' different.

Output data

Display the names of K most advanced students in lexicographical order (in alphabetical order). Each name appears on a separate line.

Examples

Input example #1
1 1
d 1
Output example #1
d