CIT have at most m scholarships for their students. They will choose best students with highest GPA in the school year. Students can take a course multiple times, the greatest grade will be his/her final grade 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^5)~.

• Each of the next ~n~ lines contains student's identity, course's code and overall score. Student's 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 and increasing of identity. Each student includes the student's rank, identity and GPA (rounded to whole integer). If two students have same GPA (not rounded), they will get scholarships together or none of them get scholarships.

Sample Input

8 3
1 1 10
1 2 50
1 1 60
1 2 45
2 1 55
3 1 100
3 2 80
4 1 90

Sample Output

1 3 90
1 4 90