Timestamped key-value store: return each key's latest value at or before a query time

Implement a key-value store that keeps every version of a value. Setting a key records a value at a given timestamp; reading a key at a timestamp returns the value recorded for that key at the latest timestamp that is less than or equal to the query time, or an empty string if there is none. For this console version, the operations arrive as a list and you return the results of the reads in order. ### Function Signature ```python def run_time_map(operations: list[list[str]]) -> list[str]: ``` ### Rules - Each operation is either `["set", key, value, timestamp]` or `["get", key, timestamp]`; timestamps are written as decimal integer strings. - Operations are applied in list order, and a `get` sees only the `set` operations that appear before it in the list. - `["get", key, t]` returns the value of the earlier `set` on the same key with the greatest timestamp that is `<= t`. If no such `set` exists, it returns `""`. - Return one string per `get`, in the order the `get` operations appear. `set` operations produce no output. ### Constraints - `1 <= len(operations) <= 2 * 10^5` - `1 <= len(key) <= 100` and `1 <= len(value) <= 100`; keys and values contain only lowercase English letters and digits - `1 <= timestamp <= 10^7` for both operation types - Timestamps of `set` operations are strictly increasing across the whole list, so they are also strictly increasing for each key; `get` timestamps can appear in any order. ### Examples Example 1 ```text operations = [["set", "cfg", "v1", "1"], ["get", "cfg", "1"], ["get", "cfg", "3"], ["set", "cfg", "v2", "4"], ["get", "cfg", "4"], ["get", "cfg", "3"], ["get", "app", "5"]] output = ["v1", "v1", "v2", "v1", ""] ``` At time 3 the latest version of `cfg` is still `v1`. After `v2` is set at 4, a read at 4 returns `v2`, while a read at 3 still returns `v1`. Key `app` was never set. Example 2 ```text operations = [["set", "a", "x", "2"], ["get", "a", "1"], ["set", "b", "y", "3"], ["get", "b", "9"], ["get", "a", "9"]] output = ["", "y", "x"] ``` The first read asks for a time before `a` had any value, so it returns the empty string.