from structures import run_operations

class TimeMap:
    def __init__(self):
        self.histories = {}

    def set(self, key, value, timestamp):
        history = self.histories.setdefault(key, [])
        if history and timestamp < history[-1][0]:
            raise ValueError('timestamps must be nondecreasing per key')
        history.append((timestamp, value))

    def get(self, key, timestamp):
        history = self.histories.get(key, ())
        left, right = 0, len(history)
        while left < right:
            mid = (left + right) // 2
            if history[mid][0] > timestamp:
                right = mid
            else:
                left = mid + 1
        return history[left - 1][1] if left else ''