Implement time-versioned KV store with restore

Design and implement an in-memory key–value store where every operation is associated with a timestamp (monotonically increasing integer). The store must support time-travel queries and rollback.

Implement the following operations (you may choose function signatures, but the semantics must match):

1. set(key, value, ts): Set key to value effective at time ts.
2. get(key, ts): Return the value of key at time ts (the most recent set at or before ts that hasn’t been deleted by time ts). Return null/None if the key does not exist at ts.
3. delete(key, ts): Delete key effective at time ts.
4. Range query requirement: support querying a time interval for a key, e.g. getRange(key, startTs, endTs), returning the value history within [startTs, endTs] (for example, a list of segments or (timestamp, value) change points within the interval).
5. restore(ts): Restore the entire store to exactly the state it had at time ts (after all operations with timestamp <= ts), discarding the effects of any operations with timestamp > ts.

Discuss and/or implement data structures that make these operations efficient. Clarify any assumptions (e.g., whether multiple operations may share the same timestamp, and how ties are resolved).

Implement Time-Versioned KV Store with Restore

You are given a sequence of operations for an in-memory time-versioned key-value store. Implement a function solution(operations) that processes the operations in order and returns the answers for every get and getRange query.

Operations are represented as tuples:

• ("set", key, value, ts): set key to value effective at timestamp ts.
• ("get", key, ts): return the value visible for key at time ts, or None if the key does not exist at that time.
• ("delete", key, ts): delete key effective at timestamp ts.
• ("getRange", key, startTs, endTs): return the visible value history for key inside [startTs, endTs] as a list of [timestamp, value] change points.
• ("restore", ts): restore the entire store to exactly the state it had after all mutations with timestamp <= ts, permanently discarding every mutation with timestamp > ts.

Important clarifications:

• Process operations in input order.
• Only set and delete create historical changes.
• get and getRange are queries only; they do not change history.
• restore truncates the current timeline; discarded future mutations do not come back later.
• Mutation timestamps (set/delete) are non-decreasing in input order. Equal timestamps are allowed.
• If multiple mutations share the same timestamp, input order breaks ties: the later mutation is the visible one at that timestamp.
• For getRange, return visible change points, not every raw mutation. If the key already exists at startTs, include [startTs, value_at_startTs] as the first entry. Then include later timestamps in (startTs, endTs] where the visible value changes. Deletions are represented by None.

Your goal is to support these operations efficiently.

Constraints

• 0 <= len(operations) <= 2 * 10^5
• 0 <= ts, startTs, endTs <= 10^9
• Timestamps of set and delete operations are non-decreasing in input order
• Equal mutation timestamps are allowed; later input order wins for that timestamp
• Keys are strings; values can be any Python value comparable with ==

Examples

Example 1

Input: [("set", "a", "x", 1), ("set", "a", "y", 4), ("get", "a", 3), ("getRange", "a", 1, 5), ("delete", "a", 6), ("get", "a", 6)]
Output: ["x", [[1, "x"], [4, "y"]], None]

Explanation: At time 3, a is x. The range [1, 5] shows a starting as x and changing to y at time 4. After deleting at time 6, get(a, 6) returns None.

Example 2

Input: [("set", "a", 10, 1), ("set", "b", 20, 2), ("set", "a", 30, 5), ("get", "a", 5), ("restore", 2), ("get", "a", 5), ("get", "b", 100), ("getRange", "a", 1, 10)]
Output: [30, 10, 20, [[1, 10]]]

Explanation: Before restore, a is 30 at time 5. Restoring to time 2 discards the change at time 5, so later queries see a = 10 and b = 20. The only visible history for a is its value from time 1.

Hints

1. Store, for each key, a sorted history of its mutations. Because mutation timestamps are non-decreasing, you can append instead of inserting.
2. To make restore(ts) efficient, keep a global stack of applied mutations and pop mutations from the end while their timestamp is greater than ts.