Time-Travel Key-Value Store

Build a TimeStore class: a key-value store that keeps the whole history of every key, so you can ask what a key held at any moment.

• set(key, value, t) records that from time t on, key holds value.
• delete(key, t) records that from time t on, key holds nothing.
• get(key, t) returns what key held at time t: the value of the latest write (set or delete) for that key with a time at or before t. Return None if that write was a delete, or if there is no such write.

Writes can arrive in any time order, so history can be filled in later. If a key gets two writes with the same time, the later call replaces the earlier one.

Examples

s = TimeStore()
s.set('door', 'open', 10)
s.set('door', 'closed', 20)
s.get('door', 15)     # returns 'open'
s.get('door', 25)     # returns 'closed'
s.get('door', 5)      # returns None
s.delete('door', 30)
s.get('door', 31)     # returns None
s.set('door', 'ajar', 12)
s.get('door', 15)     # returns 'ajar'

The last write fills in history: at time 15, the latest write at or before 15 is now the one at time 12.

Constraints

• Keys and values are strings; times are whole numbers from 0 to 10^9
• Up to 20,000 calls in total, so get should not look through a key's whole history