Time Based Key-Value Store

Design a store supporting set key value timestamp and get key timestamp. get returns the value stored with the largest timestamp that is less than or equal to the given timestamp, or an empty line if none exists. Timestamps for a key are strictly increasing in set calls.

1 <= q <= 2 * 10^5