EIU Programming Practices and Exams

This quarter, a university will give at most m special scholarships to the best students who meet criteria: earn at least k credits (each passed courses is 4 credits), and GPA equals or greater p. Output the list of students gets the scholarship.

Input

The first line contains 4 integer n, m, k, p (n ≤ 10⁵) which are the number of students, the number of scholarships, the minimum number of credits and the required GPA.

In the next n lines, each represents a student:

• Student's name (including lower case letters and not exceeding 20 characters).
• c, the number of courses that the student took (1 ≤ c ≤ 30)
• c integers which are scores of c courses (c_i ≤ 100)

Output

The list of students sorted in the decreasing order of average score and increasing name. If two students have the same average scores should both receive scholarships, or none of them receive scholarship.

Example

Input:
6 3 8 75 
nam 2 80 90
an 2 90 90
ngoc 2 100 40
duc 1 100
khanh 2 100 90
phi 2 90 80


Output:
khanh 95
an 90