Problem A
Flyafgange

Vedligehold afgangstavlen på verdens travleste lufthavn. Hver afgang består af et planlagt tidspunkt og en destination; afgangstidspunkterne er unikke i den forstand, at der aldrig afgår to fly på samme tidspunkt.

Du skal kunne håndtere følgende operationer:

Aflysninger:

Formatet er »cancel $s$«. Aflys den planlagte afgang kl. $s$.

Forsinkelser:

The format is »delay $s$ $d$«. Den planlagte afgang kl. $s$ forsinkes med $d$ sekunder.

Omdirigering:

Formatet er »reroute $s$ $c$«. Den planlagte afgang kl. $s$ omdirigeres til destinationen $c$.

Destination?

Formatet er »destination $t$«. Er der planlagt en afgang kl. $t$; og i så fald hvorhen?

Næste afgang?

Formatet er »next $t$«; denne forespørgsel forekommer kun i testgrupper 2 og 4. Hvorhen går den næste afgang? Mere nøjagtig, hvad er den tidligst planlagte afgang $s$ med $s\ge t$.

Tæl afgange.

Formatet er »count $t_1$ $t_2$«; denne forespørgsel forekommer kun i testgrupper 2 og 4. Hvor mange afgange er planlagte inden for et vist tidsrum? Mere nøjagtigt, hvor mange eksisterende afgangstider $s$ opfylder $t_1\le s\le t_2$?

Indlæsning

Indlæsningen begynder med det oprindelige antal $n$ af flyafgange og antallet $m$ af operationer. De følgende $n$ linjer indeholder en flyafgang hver, bestående af et afgangstidspunkt og navnet på en destination, adskilt af et mellemrum. Afgangstiderne er i voksende orden.

Derpå følger $m$ linjer med operationer, som skal udføres i den givne rækkefølge. Alle tidspunkter $t$, $s$, $t_1$ og $t_2$ er på formatet tt:mm:ss; der forekommer ingen tidspunkter før 00:00:01 eller efter 23:59:59. Du kan antage $t_1\le t_2$. Planlagte afgangsider $s$ opfylder, at der findes en afgang kl. $s$, når operationen skal udføres. Forsinkelsen $d$ er et heltal med $d>0$; du kan antage, at $s+d$ er »ledigt« i den forstand at ingen anden afgang er planlagt til dette tidspunkt, og at det ikke er efter kl. 23:59:59. Du kan antage, at svaret til »next« er veldefineret, dvs. at der findes en planlagt afgang kl. $s$ for noget $s\ge t$.

Navnet $c$ på en destination består af 7 bogstaver fra det engelske alfabet.

Udskrift

Udskriv svarene til hver forespørgsel, et per linje, i samme rækkefølge. Destinationen for et tidspunkt, hvor der ikke er en planlagt afgang, er et enkelt minustegn »-«. Destinationsnavne er versalfølsomme.

Testgrupper

Der er fire testrupper

14 10
09:00:00 Chicago
09:00:03 Phoenix
09:00:13 Houston
09:00:59 Chicago
09:01:10 Houston
09:03:13 Chicago
09:10:11 Seattle
09:10:25 Seattle
09:14:25 Phoenix
09:19:32 Chicago
09:19:46 Chicago
09:21:05 Chicago
09:22:43 Seattle
09:22:54 Seattle
destination 09:00:03
destination 09:21:45
destination 09:14:25
cancel 09:14:25
destination 09:14:25
delay 09:00:59 1
destination 09:00:59
destination 09:01:00
reroute 09:01:00 Houston
destination 09:01:00

Phoenix
-
Phoenix
-
-
Chicago
Houston

14 3
09:00:00 Chicago
09:00:03 Phoenix
09:00:13 Houston
09:00:59 Chicago
09:01:10 Houston
09:03:13 Chicago
09:10:11 Seattle
09:10:25 Seattle
09:14:25 Phoenix
09:19:32 Chicago
09:19:46 Chicago
09:21:05 Chicago
09:22:43 Seattle
09:22:54 Seattle
next 09:21:45
next 09:22:54
count 09:00:30 09:10:25

09:22:43 Seattle
09:22:54 Seattle
5

1 2
12:00:00 Seattle
cancel 12:00:00
count 11:00:01 12:59:59

0

2 9
11:00:00 Chicago
12:00:00 Seattle
delay 12:00:00 3600
delay 13:00:00 3600
reroute 14:00:00 Spokane
destination 12:00:00
destination 13:00:00
destination 14:00:00
delay 11:00:00 3600
destination 11:00:00
destination 12:00:00

-
-
Spokane
-
Chicago