Time-based key-value store

Design a store that keeps multiple timestamped versions of each key and answers point-in-time queries:

• set(key, value, timestamp), record value for key at timestamp (timestamps for a given key arrive strictly increasing).
• get(key, timestamp), return the value whose stored time is the largest one <= timestamp; return "" if none exists (or the key is unknown).

tm.set("px", "100", 1)
tm.set("px", "105", 4)
tm.get("px", 1)  -> "100"
tm.get("px", 3)  -> "100"      # nothing newer than t=3
tm.get("px", 4)  -> "105"
tm.get("px", 5)  -> "105"      # latest at-or-before t=5

get should be $O(\log m)$ where m is the number of versions for that key.