Problem A
Flights

Maintain the flight schedule at the worlds’s busiest airport. Each flight consists of a scheduled departure time and a destination; departure times are unique in the sense that no two flights leave at the same time.

You need to handle the following operations:

Cancellation:

The format is “cancel $s$”. Cancel the flight scheduled for time $s$.

Delays:

The format is “delay $s$ $d$”. Delay the flight scheduled for time $s$ by $d$ seconds.

Rerouting:

The format is “reroute $s$ $c$”. Reroute the flight scheduled for time $s$ to destination $c$.

Destination?

The format is “destination $t$”. Is there a flight scheduled for time $t$, and if so, what is its destination.

Next departure?

The format is “next $t$”; this query appears in test groups 2 and 4 only. What is the next departure? More precisely, what is the earliest scheduled departure $s$ such that $s\geq t$?

Count flights.

The format is “count $t_1$ $t_2$”; this query appears in test groups 2 and 4 only. How many departures are scheduled in an interval? More precisely, what is the number of scheduled departures $s$ with $t_1\leq s\leq t_2$?

Input

The input starts with the original number $n$ of flights and the number of operations $m$. The following $n$ lines each contain a flight, consisting of a departure time followed by the name of a destination, separated by a single space. The departure times are in ascending order.

Then follow $m$ lines of operations, which have to be executed in the given order. All times $s$, $t$, $t_1$ and $t_2$ are in the format hh:mm:ss; no time is before 00:00:01 or after 23:59:59. You can assume $t_1\leq t_2$. Scheduled times $s$ are guaranteed to exist, in the sense that some departure is scheduled for time $s$ at the moment the operation is executed. The delay $d$ is a nonzero, positive integer and given in seconds; you can assume that the delayed time $s+d$ is “free,” in the sense that no other flight is currently scheduled for that time, and no later than 23:59:59. You can assume that the answer to “next” is well defined, i.e., there exists a departure scheduled for $s$ with $t\leq s$.

The name $c$ of a destination is a 7-letter word using letters from the English alphabet.

Output

The answers to the query operations, one per line, in order of appearance. The answer to a destination query for a time where there is no scheduled departure is a single hyphen “-”. Destination names are case-sensitive; times must be given in the specified format.

Test groups

There are 4 different test groups.

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