Design a Versioned Key-Value Store

Implement a data structure for storing values by key over time. The structure should support these operations: - `put(key, value, timestamp)`: Store the string `value` for the string `key` at the given integer `timestamp`. - `get(key, timestamp)`: Return the value associated with `key` at the greatest timestamp less than or equal to `timestamp`. If there is no stored value for `key` at or before the requested time, return an empty string. Assumptions: - `key` and `value` are non-empty strings. - `timestamp` is a positive integer. - Calls to `put` are given in strictly increasing timestamp order. Example: - `put("foo", "bar", 1)` - `get("foo", 1)` returns `"bar"` - `get("foo", 3)` returns `"bar"` - `put("foo", "baz", 4)` - `get("foo", 4)` returns `"baz"` - `get("foo", 5)` returns `"baz"`