import collections

# 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 the TimeMap class:

# TimeMap() Initializes the object of the data structure.
# void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
# String get(String key, int timestamp) Returns a value such that set was called previously,
# with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the
# largest timestamp_prev. If there are no values, it returns "".


# constraint
# all timestamp are strictly increasing

class TimeBasedKeyValueStore:

    def __init__(self) -> None:
        self.hashmap = collections.defaultdict(list)

    def set(self, key, value, timestamp):
        self.hashmap[key].append([timestamp, value])

    def get(self, key, timestamp):
        arr = self.hashmap[key]
        left = 0
        right = len(arr)

        while left < right:
            mid = (left + right) // 2
            if arr[mid][0] <= timestamp:
                left = mid + 1
            else:
                right = mid

        return "" if right == 0 else arr[left - 1][1]
