Temporal key-value store with point-in-time reads and restore

Build an in-memory key-value store that keeps every version of every key, so you can ask what a key held at any point in time.

Implement the TemporalKVStore class:

• TemporalKVStore() creates an empty store.
• set(key: str, value, ts: int) -> None records that key holds value from time ts on.
• remove(key: str, ts: int) -> None records that key is absent from time ts on, until a later set.
• get(key: str, ts: int) -> value | None returns the value of the latest write to key with timestamp <= ts. It returns None if there is no such write or if that write was a remove.
• restore(ts: int) -> None rolls the whole store back to its state at time ts. All writes with a timestamp greater than ts are discarded permanently. New writes after a restore are allowed at any timestamp.

Rules:

• Timestamps are integers and may arrive out of order. A late write must take effect at its own timestamp. It must not change answers for earlier times, and it must not hide newer writes.
• Two writes to the same key at the same timestamp: the later call wins.
• Removing a key must not erase its history. Reads at earlier times still see the old values.
• Expect up to about 10^5 operations, mostly in timestamp order. get should be faster than a scan of the key's history.

Example

s = TemporalKVStore()
s.set("flag", "off", 100)
s.set("flag", "on", 200)
s.get("flag", 150)    -> "off"
s.get("flag", 200)    -> "on"
s.remove("flag", 300)
s.get("flag", 350)    -> None
s.set("flag", "beta", 150)   # arrives late
s.get("flag", 170)    -> "beta"
s.get("flag", 250)    -> "on"
s.restore(160)
s.get("flag", 500)    -> "beta"

Example 2

s = TemporalKVStore()
s.get("x", 10)        -> None
s.set("x", 1, 10)
s.set("x", 2, 10)     # same timestamp, last call wins
s.get("x", 10)        -> 2
s.get("x", 9)         -> None