DesignHash MapBinary Search
Design a key-value store that keeps every value a key has had over time. set key value timestamp stores a value at a time; get key timestamp returns the value that was set with the largest timestamp that is less than or equal to the requested one, or NONE if there is no such value. For each key, set is always called with increasing timestamps. You are given a list of operations.
Input
Line 1: q, the number of operations. Next q lines: set key value timestamp or get key timestamp (keys and values are lowercase words).
Output
For every get print the value, or NONE, one per line.
Constraints
1 <= q <= 10^4 0 <= timestamp <= 10^7
Example 1
Input
5 set foo bar 1 get foo 1 get foo 3 set foo bar2 4 get foo 5
Output
bar bar bar2
At time 3 the latest value is still bar; at time 5 it is bar2.