# Problem D

Running Race

Languages
da
en
You are the main organiser of an annual running race, where partipants must complete $k$ laps. The prizes are even larger than last year, and you have attracted more partipants than expected.

Every participant has a unique start number for
identification. In previous years, there was ample time to hand
out start numbers on the day of the race. But this year, every
contestant receives their start number already when they
register. Starting numbers are handed out in increasing
sequence, beginning from $1$. As a consequence, cancellations
lead to *gaps* in the sequence of start numbers on the
day of the race.

The large number of contestants also leads to other logistical challenges. One is that it would take several days to produce the final ranking by hand, so you have decided to use a computer. Write a program that computes the final ranking from the individual lap times. The race is planned in such a way that all participants will be too exhausted to continue after $k$ laps.

## Input

Three integers $l$, $k$, and $s$: how many lap times were recorded, how many laps are needed to finish the race, and how many start numbers were handed out during registration. You can assume $1 \leq l \leq 10^5$, $1 \leq k \leq 10$, and $1 \leq s \leq 10^9$.

Then follow $l$ lines,
each consisting of a start number $i$ and a lap time in the format
`mm.ss`, where $1 \leq i \leq s$. This means that the
participant with start number $i$ has completed a lap in
$mm$ minutes and
$ss$ seconds.

## Output

One line per participant who completed the race, identified by start number, and ranked from fastest to slowest. If two partipants have the same total time, rank them by start number; smallest first.

## Points

There are three test groups.

Group |
Points |
Constraints |

1 |
32 |
All partipants complete the race and $s \leq l$ |

2 |
33 |
$s \leq l$ |

3 |
35 |

Sample Input 1 | Sample Output 1 |
---|---|

6 2 3 1 01.00 2 00.59 1 01.33 3 00.54 3 02.20 2 01.02 |
2 1 3 |

Sample Input 2 | Sample Output 2 |
---|---|

8 3 3 3 03.00 1 03.57 2 02.56 3 13.33 2 04.25 3 04.29 2 03.12 1 24.47 |
2 3 |

Sample Input 3 | Sample Output 3 |
---|---|

8 2 8 6 02.52 4 04.22 6 03.03 4 02.50 5 03.30 7 02.05 7 02.36 5 02.25 |
7 5 6 4 |