Time Based Key-Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement a function that processes a list of operations:

• set(key, value, timestamp) — Stores the key with the value at the given timestamp.
• get(key, timestamp) — Returns a value such that set was called previously with timestamp_prev <= timestamp. If there are multiple such values, return the value with the largest timestamp_prev. If there are no values, return "".

Examples

Example 1:

Input: ops = ["set", "get", "get", "set", "get", "get"], args = [["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output: [null, "bar", "bar", null, "bar2", "bar2"]

Example 2:

Input: ops = ["set", "set", "get", "get", "get"], args = [["love", "high", 10], ["love", "low", 20], ["love", 5], ["love", 10], ["love", 15]]

Output: [null, null, "", "high", "high"]

Constraints

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits
• 1 <= timestamp <= 10^7
• All timestamps of set are strictly increasing for the same key
• At most 2 * 10^5 calls to set and get