Problem F
Running Race

Runners

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.

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

2
1
3

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

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