Time Based Key-Value Store

Design a class TimeMap that stores multiple values for the same key at different times and can answer "what was the value of this key at time t?".

• TimeMap() creates an empty store.
• set(key, value, timestamp) records that key had value starting at timestamp. Earlier values for the key are kept, not overwritten.
• get(key, timestamp) returns the value from the set call for key with the largest timestamp that is <= timestamp. If key was never set, or every write for it is later than timestamp, return the empty string "".

Timestamps passed to set are strictly increasing across all calls, so each key's history arrives already sorted by time.