DMPG '17 G4 - Timeline

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Harold is, like the rest of his coworkers, working hard to ensure all records are "accurate". To do this they must change some labels here and there, but more importantly, change the time that certain events occurred... in the database.

Unfortunately for you, many students are looking up "information" for their projects at the same time, and all the queries are grouped together. You wouldn't want to keep them waiting.

The timeline begins with events, each occurring at a distinct time and having a label . Initially the search filter allows all events to pass. There will be queries, which will be one of the following:

• T a b - find the event which occurred at time and change it so it occurred at time .
• L a b - find the event which occurred at time and change its label to .
• F s v - change the filter. If s is <, allow only events with labels below to pass, if s is >, allow only events with labels above to pass, and if s is ., reset the filter to none and ignore .
• S v - find the event which occurred at time closest to and passing the filter. If there is a tie, choose the later one. Output this event's time.

,

Input Specification

The first line will contain .

The next lines will each contain and separated by a space.

The following line will contain .

The next lines will each contain a query in the form described above.

Output Specification

The result of each query, one per line.

Sample Input

5
-2 1
0 4
3 -1
4 3
7 4
13
S -1
F > 3
S -4
S 4
T 7 9
S 4
F < -2
L 9 -3
S -3
F . 0
S 2
T 3 -3
S -3

Sample Output

0
0
7
0
9
3
-3

Explanation

The closest event to is .

The filter is set to .

The closest event to is , but is not greater than , and for the next closest, , its label is greater than .

The closest event to is , but is not greater than , and for the next closest, , its label is greater than .

The time of event is changed to .

The closest event to with label greater than is now .

The filter is set to . No events pass, but that is okay.

The label of event is changed to . Now it passes the filter.

The closest event to which passes the filter is .

The filter is cleared.

The closest event to is .

The time of event is changed to .

The closest event to is .