Time Based Key-Value Store

Design a store that keeps multiple values for a key at different timestamps and answers time-based queries. Process a sequence of operations. Input format: - First line: q - Next q lines: one operation each, one of: - `set key value timestamp` — store value for key at the given timestamp - `get key timestamp` — print the value whose timestamp is the largest value not exceeding the query timestamp; print `EMPTY` if no such value exists For each key, `set` is called with strictly increasing timestamps. Keys and values are non-empty tokens of lowercase letters and digits. Print one line per `get` operation.

1 <= q <= 10^5
1 <= timestamp <= 10^7
1 <= key.length, value.length <= 100

6
set foo bar 1
get foo 1
get foo 3
set foo bar2 4
get foo 4
get foo 5

bar
bar
bar2
bar2

1
get a 1

EMPTY