King Arthur II has problems with pronouncing the digit 3. People are afraid of presenting something which includes 3 in it. The solution found is that if any number includes 3 as a digit, the number is divided by 2. This process continues as far as the new numbers include new 3s.
You are working as assistant director in South East Town School and you need to present information to the King. In the brief, you will show top k students according to the graduation exam results. However, if the King Arthur II wants to see the entire list, you are to show the entire list. So, you need to make sure that no student grades includes 3 in it.
Question: Write a program that will get n students information. You will show top k student information, after preparing "the proper list” ☺
Input specification
First you will be given two integers (n) the number of students and (k) the top students to show in your brief where 1 ≤ n ≤ 40,000 and 1 ≤ k ≤ 10,000. Then in the following n lines you will be given n student information. Every line has:
• ID of student: an integer between 1 and 1e6
• Name and surname of the student: at most 50 char including English letters and digits and and space. Some students might have middle names. Name and surname ends with a semicolon.
• Grade point of student: an integer less than 10,000
Output specification
Show name surname and grades of top k students. If two students have the same points, the student with the greater ID comes first.
Sample Input I
6 3
5 Thelma Campbell; 243
7 Brenda Gordon; 315
9 Pablo Mathis; 1454
12 Lila Sullivan; 89
15 Tasha Angelo Moss; 536
17 Michael Davis; 1693 Sample Output I
Pablo Mathis 1454
Michael Davis 846
Tasha Angelo Moss 268
Explanation: Here is the list after processing and sorting.
• Pablo Mathis 1454
• Tasha Angelo Moss 268
• Michael Davis 168
• Brenda Gordon 157
• Thelma Campbell 121
• Lila Sullivan 89