Time-Based Key-Value Store II

Create a key-value storage class indexed by timestamps. It must provide __init__(), set(key: str, value: str, timestamp: int) -> None, and query(key: str, timestamp: int) -> str.

• __init__() takes no arguments and prepares the initial state for every key.
• set(key: str, value: str, timestamp: int) -> None stores the value for the given key and timestamp.
• query(key: str, timestamp: int) -> str should retrieve the value matching the given key and timestamp. Return an empty string when no matching value is available.

Aim for the best possible time and memory efficiency.

Constraints

• Combined input-string length is at most 10^5.
• timestamp is in the interval [1, 10^7].

Diagram

Internal data structure for the timestamp key-value store.

Example

Input:
set('apple', 'red', 2)
query('apple', 2)
query('apple', 4)
set('apple', 'green', 6)
query('apple', 6)
query('apple', 8)
Output:
red
red
green
green

Example

Input: set('pear', 'yellow', 3)
query('pear', 3)
Output:
yellow