시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 5 3 3 60.000%

문제

ICPC Regional contest results are determined by the final team standings after a regional contest. A regional contest consists of some number of problems that are to be solved by some number of teams.

Teams are ranked according to the most problems solved. Teams who solve the same number of problems are ranked by least total time. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the first accepted run plus 20 penalty minutes for every previously rejected run for that problem. There is no time consumed for a problem that is not solved. In the event of ties, the team with the smaller time consumed of the last correctly submitted solution ranks higher. That process is repeated as needed (2nd to last correctly submitted problem, 3rd to last correctly submitted problem, etc.) If there is still a tie after all tie-breakers have been exhausted, the teams are ranked equally and displayed in team number order. For example, if there are 3 teams in a contest, and teams 1 and 3 both rank 1, then team 2 would be rank 3 (there is no rank 2 in this case).

For this problem you will write a program to print the final standings of a contest based on the supplied input.

입력

The first line of input contains four space separated integers that define the contest parameters: NT NP NS NR for number of teams, number of problems, number of submissions and number of highest rank to display respectively. (2 ≤ NT ≤ 100), (1 ≤ NP ≤ 20), (1 ≤ NS ≤ 10000), (1 ≤ NRNT). Note that it is possible that the highest ranked team(s) actually displayed could be less than NR.

The next NS lines each contain four space separated integers the describe submissions. Each submission line has T P t D for team number, problem number, time submitted and disposition respectively. The time submitted is the number of minutes since the start of the contest. (1 ≤ TNT), (1 ≤ PNP), (0 ≤ t < 300), D = 0 or 1 as to whether the submission rejected (wrong) or accepted (correct) respectively. The value of t will never be less than the previous line’s value for t. Any submissions with t ≥ 300 should be ignored.

출력

The output will consist of the ranked standings (best to worst) for the contest showing all teams with rank 1 through NR. Each line will contain 16 characters grouped in four columns. The first column is the rank left justified in a four-character field. The second column is the team number left justified in a four-character field. The third column is the number of problems solved in a right justified three-character field. The fourth column is the total time right justified in a five-character field.

예제 입력 1

50 12 45 2
16 1 2 1
50 1 5 1
3 1 5 1
16 11 8 0
16 7 10 1
3 7 11 1
50 7 11 1
16 8 14 1
3 11 16 0
3 9 24 1
50 8 27 1
16 11 29 0
50 11 39 1
16 9 41 1
3 8 42 1
50 9 50 1
3 11 52 1
3 10 56 1
16 5 62 1
16 11 72 1
3 3 75 1
50 3 77 1
16 3 103 1
3 3 132 0
3 5 138 1
16 2 147 0
16 2 155 0
16 10 169 1
16 2 188 0
16 2 197 1
50 5 232 1
3 4 253 1
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
50 10 270 0
3 6 299 1
50 10 299 1

예제 출력 1

1   3    10  975
2   16    9  770