Simplified Time-Based Key-Value Store

Implement a simplified time-based key-value store. Support the following operations: set key value timestamp: Store string value for string key key at timestamp. get key timestamp: Return the value associated with key at the largest timestamp that is less than or equal to timestamp. If no such timestamp exists for the key, return an empty string. Assume that timestamps passed to set are strictly increasing for each individual key. Input Format The first line contains an integer q, the number of operations. Each of the next q lines is one operation: set key value timestamp or: get key timestamp Output Format For every get operation, print its result on a separate line. Print an empty line for an empty-string result. Constraints 1 <= q <= 2 * 10^5 1 <= timestamp <= 10^9 key and value contain no spaces and have length at most 100. Example Input: 6 set foo bar 1 get foo 1 get foo 3 set foo bar2 4 get foo 4 get foo 5 Output: bar bar bar2 bar2 Example Input 6 set foo bar 1 get foo 1 get foo 3 set foo bar2 4 get foo 4 get foo 5 Output bar bar bar2 bar2