EIU Programming Page for CIT

CIT have at most m scholarships for their students. They will choose best students with highest GPA in the school year. Note that students can take a course multiple time. The result of the last time a student takes a course will be his/her result for that course. Student’s GPA is calculated based on courses that he/she got at least 50. Given the result of students in order of increasing time, find out the list of students who will achieve the scholarship.

Input

The first line contains two integers n and m.  (m ≤ n ≤ 10⁵).

Each line in the next n lines contains student’s identity, course’s code and overall score. Student’ identity is a string contains at most 10 digits. Course’s code is an integer have at most 9 digits and overall score is between 0 and 100 (inclusive).

Output

The list of students received the scholarships in the order of decreasing GPA. Each student includes the student’s identity and GPA (rounded to whole integer). Note that if two students have same GPA (not rounded), they will get scholarships together or none of them get scholarships.

Sample