Hide

Problem D
Kapløb

Languages da en
/problems/kaploeb/file/statement/da/img-0001.jpg
Løbere
Du er hovedarrangør for et stort årligt kapløb, hvor deltagerne skal løbe en planlagt rute $k$ gange. Præmierne er de største i løbets historie, og det har tiltrukket flere deltagere end forventet.

Hver deltager skal have et unikt startnummer, som deltageren kan identificeres med. Tidligere har der været tid til at tildele disse på løbsdagen, men det ser der ikke ud til at blive i år. Derfor får hver deltager sit startnummer ved tilmelding. Disse uddeles i stigende rækkefølge startende fra nummer 1. Konsekvensen af dette er, at eventuelle afbud vil medføre huller i sekvensen af startnumre på løbsdagen.

Det store deltagerantal medfører også andre logistiske problemer. Et af dem er, at det vil tage flere dage at fabrikere den endelige rangering blandt deltagerne i hånden, så i stedet tyr du til din kære ven, datamaten. For at finde ranglisten rangeres deltagerne efter summen af sine rundetider, hvor det er bedst at være hurtigst.

Skriv et program der ud fra deltagernes rundetider kan udregne den endelige rangering.

Ruten er i år tilrettelagt sådan, at alle deltagere vil være for udmattede til at løbe videre, efter at have løbet de $k$ runder.

Indlæsning

Tre heltal $l$, $k$ og $s$, der henholdvis beskriver hvor mange rundetider der er skrevet ned, hvor mange runder deltagerne skulle løbe for at fuldføre løbet, og hvor mange startnumre der er uddelt ved tilmeldingen. Du kan antage $1 \leq l \leq 10^5$, $1 \leq k \leq 10$ og $1 \leq s \leq 10^9$.

Derefter følger $l$ linjer, der hver består af et startnummer $i$ og en rundetid i formatet mm.ss, hvor $1 \leq i \leq s$. Dette indikerer at løberen med startnummer $i$ har løbet en runde på $mm$ minutter og $ss$ sekunder.

Udskrift

En linje for hver deltager der har fuldført løbet (identificeret med startnummer), rangeret fra hurtigst til langsomst. Hvis 2 deltagere har løbet lige hurtigt, rangeres de efter startnummer, hvor det laveste er først.

Pointsætning

Der er tre testgrupper.

Gruppe

Point

Begrænsninger

1

32

Alle fremmødte deltagere fuldfører løbet og $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