Create a timebased key-value store class TimeMap, that supports two operations.
1. set(string key, string value, int timestamp)

Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
If there are multiple such values, it returns the one with the largest timestamp_prev.
If there are no values, it returns the empty string ("").

 

Example 1:
Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"   



Example 2:
Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]



 
Note:

All key/value strings are lowercase.
All key/value strings have length in the range [1, 100]
The timestamps for all TimeMap.set operations are strictly increasing.
1 <= timestamp <= 10^7
TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

Difficulty: interview

Starter code:

class TimeMap:
    def __init__(self):
        """
        Initialize your data structure here.
        """
    def set(self, key: str, value: str, timestamp: int) -> None:
    def get(self, key: str, timestamp: int) -> str:
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

Solutions:
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = {}
        self.times = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store: 
            self.store[key] = [value]
            self.times[key] = [timestamp]
        else:
            self.store[key].append(value)
            self.times[key].append(timestamp)
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store: return \"\"
        else:
            lst = self.times[key]
            
            if timestamp < lst[0]: return \"\"
            elif timestamp >=lst[-1]: return self.store[key][-1]
            else:
                l = 0
                r = len(lst)-1
                while l < r:
                    mid = (l+r)//2
                    if lst[mid] < timestamp: r = mid
                    elif lst[mid] == timestamp: return self.store[key][mid]
                    else: l = mid
                        
                
            
            return self.store[key][r]
                


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.times = collections.defaultdict(list)
        self.values = collections.defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp) # append = O(1)
        self.values[key].append(value) # append = O(1)

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect_right(self.times[key],timestamp) # bisect_right = O(logN)
        return self.values[key][i-1] if i else '' # index of dict and then list = O(1) + O(1) = O(1)
        
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kv=dict()

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.kv:
            self.kv[key].append((timestamp,value))
        else:
            self.kv[key]=[(timestamp,value)]

    def get(self, key: str, timestamp: int) -> str:
        if key in self.kv:
            l=self.kv[key]
            for i in range(len(l)-1,-1,-1):
                if l[i][0]<=timestamp:
                    return l[i][1]
        return ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.mapping = collections.defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        lists = self.mapping[key]
        if not lists:
            self.mapping[key] = [(timestamp, value)]
            return
        start, end = 0, len(lists) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if lists[mid][0] == timestamp:
                self.mapping[key][mid] = (timestamp, value)
                return
            elif lists[mid][0] < timestamp:
                start = mid
            else:
                end = mid
                
        if lists[end][0] == timestamp:
            lists[end] = (timestamp, value)            
            self.mapping[key] = lists
            return
        if lists[end][0] < timestamp:
            lists.insert(end + 1, (timestamp, value))
            self.mapping[key] = lists
            # print(self.mapping)
            return
        if lists[start][0] == timestamp:
            lists[start] = (timestamp, value)            
            self.mapping[key] = lists
            return
        if lists[start][0] < timestamp:
            lists.insert(start + 1, (timestamp, value))
            self.mapping[key] = lists
            return
        
        
   

    def get(self, key: str, timestamp: int) -> str:
        lists = self.mapping[key]
        if not lists:
            return ''
        start, end = 0, len(lists) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if lists[mid][0] == timestamp:
                return lists[mid][1]
            elif lists[mid][0] < timestamp:
                start = mid
            else:
                end = mid
                
        if lists[end][0] <= timestamp:
            return lists[end][1]
        if lists[start][0] <= timestamp:
            return lists[start][1]
        return ''
    

    
    def insert(self, lists, tup):
        if not lists:
            return [tup]
        i = 0
        # print(lists)
        while i < len(lists):
            if lists[i][0] < tup[0]:
                i += 1
            elif lists[i][0] == tup[0]:
                lists[i] == tup
                return lists
            else:
                lists.insert(i, tup)
                return lists
        lists.append(tup)
        return lists


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
class TimeMap:
    def __init__(self):
        self.d = defaultdict(list)

    def set(self, key, value, timestamp):
        self.d[key].append([timestamp, value])
        
    def get(self, key, timestamp):
        start, end = 0, len(self.d[key]) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.d[key][mid][0] == timestamp:
                return self.d[key][mid][1]
            elif self.d[key][mid][0] < timestamp:
                start = mid
            else:
                end = mid
        if self.d[key][end][0] <= timestamp:
            return self.d[key][end][1]
        if self.d[key][start][0] <= timestamp:
            return self.d[key][start][1]
        return ''        

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.time_map = defaultdict(list)
    
    def binarySearch(self, arr, target):
        low, high = 0, len(arr)-1
        while low <= high:
            mid = low + (high - low)//2
            if arr[mid][0] == target:
                return mid
            elif arr[mid][0] < target:
                low = mid + 1
            else:
                high = mid - 1
        return low-1
    
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.time_map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.time_map.get(key, None)
        if not arr: return \"\"
        i = self.binarySearch(arr, timestamp)#bisect.bisect(arr, (timestamp, chr(127)))
        return arr[i][1] if i >= 0 else \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.values, self.times = {}, {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.values:
            self.values[key], self.times[key] = [value], [timestamp]
        elif timestamp > self.times[key][-1]:
            self.values[key].append(value); self.times[key].append(timestamp)
        else:
            i = bisect.bisect_left(self.times[key], timestamp)
            self.values[key].insert(i, value); self.times[key].insert(i, timestamp)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.values or timestamp < self.times[key][0]:
            return \"\"
        return self.values[key][bisect.bisect(self.times[key], timestamp)-1]        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.timemap = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.timemap[key].append([value,timestamp])
        

    def get(self, key: str, timestamp: int) -> str:
        start=0
        end=len(self.timemap[key])-1
        mid=(start+end)//2
        while start<=end:
            if self.timemap[key][mid][1]==timestamp:
                return self.timemap[key][mid][0]
            elif self.timemap[key][mid][1]<timestamp:
                start = mid+1
            elif self.timemap[key][mid][1]>timestamp:
                end=mid-1
            mid = (start+end)//2
        if start>=len(self.timemap[key])-1:
            return self.timemap[key][end][0]
        else:
            return \"\"
        
    

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.timeTable = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.timeTable[key].append([timestamp, value])
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.timeTable:
            return \"\"
        i = bisect.bisect(self.timeTable[key],[timestamp+1])-1
        if i == -1:
            return \"\"
        return self.timeTable[key][i][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.M=collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append([timestamp,value])
        

    def get(self, key: str, timestamp: int) -> str:
        A = self.M.get(key,None)
        if A is None:
            return \"\"
        i = bisect.bisect(A,[timestamp,chr(127)])
        if i:
            return A[i-1][1]
        else:
            return \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        # save a hashmap of key => [... (value, timestamp) ...]
        self.store = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = [(value, timestamp)]
        else:
            self.store[key].append((value, timestamp))
            
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return \"\"
        else:
            # now do bst
            left = 0
            right = len(self.store[key]) - 1
            while left <= right:
                mid = (left + right) // 2
                if self.store[key][mid][1] <= timestamp:
                    # ensure that it is the largest
                    next_left = mid + 1
                    next_mid = (next_left + right) // 2
                    if next_left > right or self.store[key][next_mid][1] > timestamp:
                        return self.store[key][mid][0]
                    left = next_left
                else:
                    right = mid - 1
            return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        tup = (timestamp, value)
        if key in self.store:
            # idx = bisect.bisect_left(self.store[key], tup)
            self.store[key].append(tup)
        else:
            self.store[key] = [tup]

    def get(self, key: str, timestamp: int) -> str:
        #do binary search
        low = 0
        high = len(self.store[key])-1
        arr = self.store[key]
        
        while high != low:
            curr = (low + high)//2
            if arr[curr][0] == timestamp:
                return arr[curr][1]
            elif arr[curr][0] < timestamp:
                low = min(len(arr)-1, curr + 1)
            elif arr[curr][0] > timestamp:
                high = max(0,curr - 1)
           
        curr = (low + high)//2
        
        if arr[high][0] <= timestamp:
            return arr[high][1]
        elif high - 1 >= 0:
            if arr[high-1][0] <= timestamp:
                return arr[high-1][1]
        else:
            return \"\"
                
            
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.dic = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if(key in self.dic):
            self.dic[key].append((timestamp, value))
        else:
            self.dic[key] = []
            self.dic[key].append((timestamp, value))

    def get(self, key: str, q: int) -> str:
        if(key not in self.dic):
            return \"\"
        
        search = self.dic[key]
        
        low = 0
        high = len(search) - 1
        
        while(low <= high):
            mid = (low+high) // 2
            
            cond1 = search[mid][0] == q
            cond2 = (mid+1 >= len(search) and search[mid][0] < q)
            cond3 = (mid+1 < len(search) and search[mid][0] < q and search[mid+1][0] > q)
            
            if(cond1 or cond2 or cond3):
                return search[mid][1]
            elif(search[mid][0] > q):
                high = mid - 1
            else:
                low = mid + 1
            
        return \"\"
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((value, timestamp))
        

    def get(self, key: str, timestamp: int) -> str:
        return next((v for v,t in reversed(self.d[key]) if t <= timestamp), \"\")
    
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.values = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.values:
            self.values[key] = []
            
        self.values[key].append((value, timestamp))
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.values:
            return \"\"
        
        if timestamp < self.values[key][0][1]:
            return \"\"
        
        return self.search(key, 0, len(self.values[key]) - 1, timestamp)
    
    def search(self, key, left, right, timestamp):
        mid = (left + right) // 2

        if self.values[key][mid][1] == timestamp:
            return self.values[key][mid][0]
        
        if left > right:
            return self.values[key][right][0]
        
        if self.values[key][mid][1] > timestamp:
            return self.search(key, left, mid - 1, timestamp)
        else:
            return self.search(key, mid + 1, right, timestamp)
            
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.M = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str: 
        lo,hi = 0, len(self.M[key]) 
        while(lo < hi):
            med = lo+(hi-lo)// 2
            if self.M[key][med][0] <= timestamp: lo = med+1
            else: hi = med
        return self.M[key][lo-1][1] 
    # lo-1<len(self.M[key]) # 

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.M = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str: 
        lo,hi = 0, len(self.M[key]) - 1
        while(lo < hi):
            med = (lo + hi + 1) // 2
            if self.M[key][med][0] <= timestamp: lo = med
            else: hi = med - 1
        return self.M[key][lo][1] if lo < len(self.M[key]) and self.M[key][lo][0] <= timestamp else ''
            
        
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = defaultdict(list) # key : [(time1, value1), (time2, value2), ...]

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # binary search
        left = 0
        right = len(self.store[key]) - 1
        
        while left <= right:
            middle = (left + right) // 2
            # we want to find self.store[middle] <= timestamp and (middle == len(self.store[key]) - 1 or self.store[middle + 1] > timestamp)
            if self.store[key][middle][0] <= timestamp:
                if (middle == len(self.store[key]) - 1 or self.store[key][middle + 1][0] > timestamp):
                    return self.store[key][middle][1]
                else:
                    left = middle + 1
            else:
                right = middle - 1
        
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict 
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dct = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        arr = self.dct[key]
        if len(self.dct[key]) == 0:
            self.dct[key].append((timestamp, value))
        else:
            lo, hi = 0, len(self.dct[key]) - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if arr[mid][0] < timestamp:
                    lo = mid + 1
                else:
                    hi = mid - 1
            arr.insert(lo, (timestamp, value))
        return
            
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dct:
            return \"\"
        arr = self.dct[key]
        lo, hi = 0, len(arr) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if arr[mid][0] == timestamp:
                return arr[mid][1]
            elif arr[mid][0] > timestamp:
                hi = mid - 1
            else:
                lo = mid + 1
        return arr[hi][1] if hi != -1 else \"\"
                
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = [(value, timestamp)]
        else:
            self.store[key].append((value, timestamp))
    
    def binarySearch(self, k, t):
        arr = self.store[k]
        i = 0
        j = len(arr)-1
        
        while i <= j:
            mid = (i+j)//2
            
            if arr[mid][1] == t:
                return mid
            
            if arr[mid][1] < t and (mid+1 >= len(arr) or arr[mid+1][1] > t):
                return mid
            
            if arr[mid][1] > t:
                j = mid-1
            else:
                i = mid+1
        return -1
        
        
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ''
        
        idx = self.binarySearch(key, timestamp)
        if idx == -1:
            return ''
        
        return self.store[key][idx][0]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        # key is str, value is a list of list sorted by timestamp in increasing order
        self.records = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.records:
            self.records[key] = [[timestamp, value]]
        else:
            self.records[key].append([timestamp, value])
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.records:
            return ''
        to_search = self.records[key]
        val = self.b_search(timestamp, to_search)
        return val
        
    def b_search(self, target, array):
        start, end = 0, len(array)-1
        while start + 1 < end:
            mid = (start + end) // 2
            if array[mid][0] == target:
                return array[mid][1]
            elif array[mid][0] < target:
                start = mid
            else:
                end = mid - 1
        if array[end][0] <= target:
            return array[end][1]
        if array[start][0] <= target:
            return array[start][1]
        return \"\"
        
        
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dp = {}
    
    def binS(self, key, tar, i, j):
        if i>=j:
            return j
        mid = i + (j-i)//2
        if self.dp[key][mid][1] == tar:
            return mid
        if self.dp[key][mid][1] > tar:
            return self.binS(key, tar, i, mid-1)
        return self.binS(key, tar, mid+1, j)
        
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.dp:
            self.dp[key].append((value, timestamp))
        else:
            self.dp[key] = [(value, timestamp)]
            
        

    def get(self, key: str, timestamp: int) -> str:
        if key in self.dp:
            spot = self.binS(key, timestamp, 0, len(self.dp[key]) - 1)
            if spot == 0 and self.dp[key][spot][1] > timestamp:
                return \"\"
            if spot == len(self.dp[key]) or self.dp[key][spot][1] > timestamp:
                spot -= 1
            if self.dp[key][spot][1] > timestamp: return \"\"
            return self.dp[key][spot][0]
        else:
            return \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        tup = (timestamp, value)
        if key in self.store:
            idx = bisect.bisect_left(self.store[key], tup)
            # print(idx)
            self.store[key].insert(idx, tup)
        else:
            self.store[key] = [tup]

    def get(self, key: str, timestamp: int) -> str:
        #do binary search
        low = 0
        high = len(self.store[key])-1
        arr = self.store[key]
        
        while high != low:
            curr = (low + high)//2
            # print(\"Low:\", low, \"High:\", high, \"Curr\", curr, arr[curr][0], timestamp)
            if arr[curr][0] == timestamp:
                # print(\"returning\", arr[curr][1])
                return arr[curr][1]
            elif arr[curr][0] < timestamp:
                low = min(len(arr)-1, curr + 1)
            elif arr[curr][0] > timestamp:
                high = max(0,curr - 1)
           
        curr = (low + high)//2
        # print(\"Low:\", low, \"High:\", high, arr[curr][0], timestamp)
        
        if arr[high][0] <= timestamp:
            # print(\"returning\", arr[high][1])
            return arr[high][1]
        elif high - 1 >= 0:
            if arr[high-1][0] <= timestamp:
                # print(\"returning\", arr[high-1][1])
                return arr[high-1][1]
        else:
            # print(\"returning\", \"\")
            return \"\"
                
            
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        bisect.insort(self.d[key], (timestamp, 0, value)) 

    def get(self, key: str, timestamp: int) -> str:
        idx = bisect.bisect(self.d[key], (timestamp, 1, \"\")) - 1
        # print(self.d[key], idx)
        if idx < 0:
          return \"\"
        return self.d[key][idx][2]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dp = {}
    
    def binS(self, key, tar, i, j):
        if i>=j:
            return i
        mid = i + (j-i)//2
        if self.dp[key][mid][1] == tar:
            return mid
        if self.dp[key][mid][1] > tar:
            return self.binS(key, tar, i, mid-1)
        return self.binS(key, tar, mid+1, j)
        
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.dp:
            self.dp[key].append((value, timestamp))
        else:
            self.dp[key] = [(value, timestamp)]
            
        

    def get(self, key: str, timestamp: int) -> str:
        if key in self.dp:
            spot = self.binS(key, timestamp, 0, len(self.dp[key]) - 1)
            if spot == 0 and self.dp[key][spot][1] > timestamp:
                return \"\"
            if spot == len(self.dp[key]) or self.dp[key][spot][1] > timestamp:
                spot -= 1
            if self.dp[key][spot][1] > timestamp: return \"\"
            return self.dp[key][spot][0]
        else:
            return \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
class TimeMap:
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        arr = self.map[key]
        left = 0
        right = len(arr) - 1
        if arr[left][0] > timestamp:
            return \"\"
        elif arr[right][0] <= timestamp:
            return arr[right][1]
        else:
            # Binary search
            while left <= right:
                mid = (left + right) // 2
                if arr[mid][0] == timestamp:
                    return arr[mid][1]
                elif arr[mid][0] < timestamp:
                    left = mid + 1
                else:
                    right = mid - 1
            return arr[right][1]
        return \"\"

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.hmap = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.hmap[key].append([timestamp,value])

    def get(self, key: str, timestamp: int) -> str:
        arr = self.hmap[key]
        n = len(arr)
        low = 0
        high = n
        while(low < high):
            mid = (low + high) // 2
            if arr[mid][0] <= timestamp:
                low = mid + 1
            elif arr[mid][0] > timestamp:
                high = mid
        return \"\" if high == 0 else arr[high-1][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

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

    def set(self, key, value, timestamp):
        if key not in self.lookup:
            self.lookup[key] = [[timestamp, value]]
        else:
            self.lookup[key].append([timestamp, value])

    def get(self, key, timestamp):
        if key not in self.lookup:
            return \"\"

        values = self.lookup[key]

        # timestamp is asking for something earlier than our first timestamp
        if values[0][0] > timestamp:
            return \"\"
        # timestamp is asking for something later than our last timestamp
        elif values[-1][0] <= timestamp:
            return values[-1][1]

        left = 0
        right = len(values)
        while left <= right:
            # prevents sum overflow
            mid = left + (right-left)//2

            if values[mid][0] == timestamp:
                return values[mid][1]

            if values[mid][0] < timestamp:
                left = mid + 1
            elif values[mid][0] > timestamp:
                right = mid - 1

        # could not find, so return one before l == r
        return values[right][1]


class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dix = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dix[key].append([timestamp, value])
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dix or timestamp < self.dix[key][0][0]:
            return \"\"
        
        target = timestamp
        lo = 0
        hi = len(self.dix[key])-1
        
        while lo <hi:
            mid = lo + (hi-lo)//2
            
            if self.dix[key][mid][0] <= target and self.dix[key][mid+1][0] > target:
                return self.dix[key][mid][1]
            
            if  self.dix[key][mid][0] > target:
                hi = mid-1
            else:
                lo = mid+1
        
        return self.dix[key][hi][1] if self.dix[key][hi][0] <= target else self.dix[key][lo][1]
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.mapping = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.mapping[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect_right(self.mapping[key], (timestamp, chr(127)))
        if i:
            return self.mapping[key][i-1][1]
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    from collections import defaultdict
    
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        
        self.cache = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        self.cache[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        
        if key not in self.cache:
            return ''
        
        key_val_list = self.cache[key]
        
        # print(self.cache)
        
        l = 0
        r = len(key_val_list) - 1
        
        # find idx where key_val_list[i][0] <= timestamp
        
        if key_val_list[l][0] > timestamp:
            return ''
        
        found = None
        
        while r >= l:
            m = (r + l) // 2
            
            if key_val_list[m][0] > timestamp:
                r = m - 1
            elif key_val_list[m][0] == timestamp:
                return key_val_list[m][1]
            else:
                found = m
                l = m + 1
        
        return key_val_list[found][1]
        
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from sortedcontainers import SortedList

class TimeMap:
    
    def compare(self,a):
        return a[0]

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        
        self.ls = SortedList(key = self.compare)
        self.size = 0

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        self.ls.add([timestamp,key,value])
        self.size+=1
        

    def get(self, key: str, timestamp: int) -> str:
        
        temp = self.ls.bisect_right([timestamp])
        
        if(temp == 0 or self.size == 0):
            return \"\"
        
        if(temp == self.size or self.ls[temp][0] > timestamp):
            temp-=1
            
        
        while(temp >= 0):
            if(self.ls[temp][1] == key):
                return self.ls[temp][2]
            
            temp-=1
            
        return \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap(object):
    def __init__(self):
        self.M = collections.defaultdict(list)

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

    def get(self, key, timestamp):
        A = self.M.get(key, None)
        
        if A is None: 
          return \"\"
        print(chr(127))
        i = bisect.bisect_right(A, (timestamp, chr(127)))
        
        if i: 
          return A[i-1][1] 
        else: 
          return \"\"

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self._dict = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self._dict:
            self._dict[key] = [(value, timestamp)]
        else:
            val_time_list = self._dict[key]
            i, j = 0, len(val_time_list) - 1
            pos = 0
            while i <= j:
                mid = (i + j) // 2
                if val_time_list[mid][1] == timestamp:
                    pos = mid
                    break
                if val_time_list[mid][1] > timestamp:
                    j = mid - 1
                else:
                    i = mid + 1
            pos = j + 1
            val_time_list.insert(pos, (value, timestamp))
            self._dict[key] = val_time_list
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self._dict:
            return ''
        val_time_list = self._dict[key]
        i, j = 0, len(val_time_list) - 1
        pos = 0
        while i <= j:
            mid = (i + j) // 2
            if val_time_list[mid][1] == timestamp:
                return val_time_list[mid][0]
            if val_time_list[mid][1] > timestamp:
                j = mid - 1
            else:
                i = mid + 1
        if j >= 0: return val_time_list[j][0]
        else: return ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kv=dict()

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.kv:
            self.kv[key].append((timestamp,value))
        else:
            self.kv[key]=[(timestamp,value)]

    def get(self, key: str, timestamp: int) -> str:
        if key in self.kv:
            # l=self.kv[key]
            for i in range(len(self.kv[key])-1,-1,-1):
                if self.kv[key][i][0]<=timestamp:
                    return self.kv[key][i][1]
        return ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.records = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.records[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        item = self.records[key]
        i = len(item)
        while i > 0:
            i -= 1
            if item[i][0] == timestamp:
                return item[i][1]
            elif item[i][0] < timestamp:
                return item[i][1]
        return ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.values = defaultdict(list)
        self.times = defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.values[key].append(value)
        self.times[key].append(timestamp)

    def get(self, key: str, timestamp: int) -> str:
        idx = bisect.bisect_right(self.times[key], timestamp)
        return self.values[key][idx-1] if idx else \"\"
    
#      
#     USING BINARY SEARCH
#
#     def get(self, key: str, timestamp: int) -> str:
#         arr = self.map[key]
#         n = len(arr)
        
#         left = 0
#         right = nt
        
#         while left < right:
#             mid = (left + right) // 2
            
#             if arr[mid][0] <= timestamp:
#                 left = mid + 1
#             elif arr[mid][0] > timestamp:
#                 right = mid
                
#         return arr[right-1][1] if (right > 0) else \"\"


        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

# kv.set(\"love\", \"high\", 10); 
# kv.set(\"love\", \"low\", 20); 
# kv.get(\"love\", 5); -> \"\"
# kv.get(\"love\", 10); -> high
# kv.get(\"love\", 15); -> high
# kv.get(\"love\", 20); -> low
# kv.get(\"love\", 25); -> low



class TimeMap:
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = collections.defaultdict(list)
        
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append((timestamp, value))
                

    def get(self, key: str, timestamp: int) -> str:
        arr = self.dic[key]
        n = len(arr)
        
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid][0] <= timestamp:
                left = mid + 1
            elif arr[mid][0] > timestamp:
                right = mid - 1
        
        return \"\" if right == -1 else arr[right][1]
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

def debug(s, *args):
    pass
    # prin/t(s, args)


class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((timestamp, value))
        debug('set', key, value, timestamp)

    def get(self, key: str, timestamp: int) -> str:
        debug('get', key, timestamp)
        vals = self.d[key]
        if not vals:
            return \"\"
        
        # Binary search the right value
        lo, hi = 0, len(vals)-1
        
        idx = None
        debug('binsearch', vals, timestamp)
        while lo <= hi:
            mid = (lo+hi)//2
            debug('#', lo, hi, mid)
            
            if timestamp >= vals[mid][0] and (mid+1 == len(vals) or timestamp < vals[mid+1][0]):
                idx = mid
                break
            
            if timestamp > vals[mid][0]:
                lo = mid + 1
            else:
                hi = mid - 1

        debug('idx', idx)
        if idx != None:
            return vals[idx][1]
        return \"\"
    


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        arr = self.dict[key]
        n = len(arr)
        
        start = 0
        end = len(arr)
        
        while start < end:
            mid = (start + end) // 2
            if arr[mid][0] <= timestamp:
                start = mid + 1
            elif arr[mid][0] > timestamp:
                end = mid
                
        return \"\" if end == 0 else arr[end-1][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append([timestamp,value])
        
        

    def get(self, key: str, timestamp: int) -> str:
        arr = self.dict[key]
        n = len(arr)-1
        l = 0
        r = n
        while l <= r:
            mid = (l+r)//2
            if arr[mid][0] < timestamp:
                l = mid+1
            elif arr[mid][0] > timestamp:
                r = mid-1
            else:
                return arr[mid][1]
        return \"\" if r == -1 else arr[r][1]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import collections


class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append((value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        lt = self.dict[key]
        low = 0
        high = len(lt) - 1
        while low < high:
            mid = (low + high) // 2
            if timestamp < lt[mid][1]:
                high = mid - 1
            elif timestamp >= lt[mid][1]:
                if timestamp >= lt[mid+1][1]:
                    low = mid + 1
                else:
                    break
        if lt[low][1] <= timestamp:
            return lt[low][0]
        else:
            return \"\"
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.m = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m[key].append((value, timestamp))
        

    def get(self, key: str, timestamp: int) -> str:
        if len(self.m[key]) == 0: return ''
        lis = self.m[key]
        n = len(lis)
        l, r = 0, n-1
        m = (l+r+1)//2
        while l < r:
            if lis[m][1] == timestamp:
                return lis[m][0]
            elif lis[m][1] < timestamp:
                l = m
            else:
                r = m-1
            m = (l+r+1)//2
        return lis[m][0] if lis[m][1] <= timestamp else ''
            


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        all_values = self.dic[key]
        if not all_values:
            return \"\"
        val = \"\"
        left = 0
        right = len(all_values) -1
        while left <= right:
            middle = (left + right) // 2
            if all_values[middle][0] == timestamp:
                val = all_values[middle][1]
                break
            elif all_values[middle][0] < timestamp:
                val = all_values[middle][1]
                left = middle + 1
            else:
                right = middle - 1
                
        return val
                
    

def binarySearch(ls, t):
    n = len(ls)
    if len(ls)==0:
        return ''
    lo = 0
    hi = n-1
    while lo<hi:
        mi = math.ceil((hi+lo)/2)
        if ls[mi][1]<=t:
            lo = mi
        else:
            hi = mi-1
    if ls[hi][1]<=t:
        return ls[hi][0]
    else:
        return ''

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.mp = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.mp[key].append((value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        return binarySearch(self.mp[key], timestamp)


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append((value, timestamp))
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dict:
            return \"\"
        temp = self.dict[key]
        # print(temp)
        for i in reversed(range(len(temp))):
            if temp[i][1] <= timestamp:
                return temp[i][0]
        
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import collections
import bisect

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        values = self.store.get(key, [])
        i = bisect.bisect(values, [timestamp, chr(ord(\"z\")+1)])
        return values[i-1][1] if i > 0 else \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        insert_index = self.__binary_search(self.map[key], timestamp) + 1
        self.map[key].insert(insert_index, (value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        search_index = self.__binary_search(self.map[key], timestamp)
        if search_index == -1:
            return \"\"
        return self.map[key][search_index][0]
    
    def __binary_search(self, collection, timestamp):
        n = len(collection)
        lo, hi = 0, n-1
         
        while lo <= hi:
            mid = (lo+hi) // 2
            if mid == n-1:
                return n-1
            elif collection[mid][1] <= timestamp < collection[mid+1][1]:
                return mid
            elif collection[mid+1][1] <= timestamp:
                lo = mid + 1
            elif collection[mid][1] > timestamp:
                hi = mid - 1
        
        return -1
                

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.map:
            return ''
        values = self.map[key]
        if values[0][0] > timestamp:
            return ''
    
        l, r = 0, len(values) - 1
        while l < r:
            mid = l + (r - l + 1) // 2
            if values[mid][0] > timestamp:
                r = mid - 1
            else:
                l = mid
        
        return values[r][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        arr = self.d[key]
        
        l = 0
        r = len(arr) - 1
        closest = float('inf')
        
        while l <= r:
            mid = l + ((r-l)//2)
            if arr[mid][1] == timestamp:
                return arr[mid][0]
            elif arr[mid][1] < timestamp:
                closest = arr[mid][0]
                l = mid + 1
            else:
                r = mid - 1
        return closest if closest != float('inf') else \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.M = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        # A = self.M.get(key, None)
        # if not A:
        #     return \"\"
        # i = bisect.bisect_right(A, (timestamp,))
        # if i == 0:
        #     return \"\"
        # else:
        #     return A[i-1][1]
        
        lo,hi = 0, len(self.M[key]) - 1
        while(lo < hi):
            med = (lo + hi + 1) // 2
            if self.M[key][med][0] <= timestamp: lo = med
            else: hi = med - 1
        return self.M[key][lo][1] if lo < len(self.M[key]) and self.M[key][lo][0] <= timestamp else ''
    
        # while lo < hi:
        #     mid = (lo + hi + 1) // 2 #why + 1?
        #     if self.M[key][mid][0] <= timestamp: 
        #         lo = mid + 1
        #     else: hi = mid
        # ind = lo - 1
        # if ind < len(self.M[key]) and self.M[key][ind][0] <= timestamp:
        #     # why < len?
        #     return self.M[key][lo - 1][1]
        # else:
        #     return ''
            
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        
        self.dict = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        if key in self.dict:
            self.dict[key].append((timestamp, value))
        else:
            self.dict[key] = [(timestamp, value)]
        

    def get(self, key: str, timestamp: int) -> str:
        
        if key in self.dict:
            arr = self.dict[key]
            
            # do a binary search to find the largest val with t smaller than the timestamp
            
            l = 0
            r = len(arr) -1
            while l <= r:
                mid = l + (r-l)//2
                if arr[mid][0] <= timestamp and (mid+1 >= len(arr) or arr[mid+1][0] > timestamp):
                    # found the largest one:
                    return arr[mid][1]
                elif arr[mid][0] <= timestamp:
                    l = mid + 1
                else:
                    r = mid - 1
        
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import bisect
from collections import defaultdict
from dataclasses import dataclass, field

@dataclass(order=True)
class TimeMapValue:
    timestamp: int
    value: Any=field(compare=False)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        bisect.insort_right(self.map[key], TimeMapValue(timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect_right(self.map[key], TimeMapValue(timestamp, None))
        if i == 0:
            return \"\"
        return \"\" if i == 0 else self.map[key][i - 1].value


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap(object):

    def __init__(self):
        self.map = collections.defaultdict(list)
        

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

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


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)


class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.d:
            self.d[key].append([timestamp, value])
        else:
            self.d[key] = [[timestamp, value]]
        

    def get(self, key: str, timestamp: int) -> str:
        arr = self.d[key]
        n = len(arr)
        
        l = 0
        r = n
        
        while l < r:
            mid = (l + r) // 2
            if arr[mid][0] > timestamp:
                r = mid
            elif arr[mid][0] <= timestamp:
                l = mid + 1
        return \"\" if r == 0 else arr[r - 1][1]
            
           
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.dict:
            self.dict[key] = [[value], [timestamp]]
        else:
            self.dict[key][0].append(value)
            self.dict[key][1].append(timestamp)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dict or timestamp < self.dict[key][1][0]:
            return \"\"
        timestamps = self.dict[key][1]
        left = 0
        right = len(timestamps) - 1
        while left <= right:
            mid = (left + right) // 2
            if timestamp >= timestamps[mid]:
                left = mid + 1
            else:
                right = mid - 1
        return self.dict[key][0][right]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import bisect as b
from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.timestamps = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.timestamps[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.timestamps.get(key)
        if not arr: return \"\"
        i = b.bisect(arr, (timestamp, chr(127)))
        return arr[i-1][1] if i else \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))
        
    def get(self, key: str, timestamp: int) -> str:
        lst = self.store[key]
        #for ls in lst[::-1]:
        #    if ls[0] <= timestamp:
        #        return ls[1]
        left, right = 0, len(lst) -1
        clsInd = -1
        while left <= right:
            mid = (left + right) // 2
            t = lst[mid][0]
            if t <= timestamp:
                clsInd = max(clsInd, mid)
                left = mid + 1
            else:
                right = mid -1
                
        return \"\" if clsInd == -1 else lst[clsInd][1]
    

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.values = defaultdict(list)  # key = [(timestamp, value), (timestamp, value)]


    def set(self, key: str, value: str, timestamp: int) -> None:
        print(f'set({key}, {timestamp}, {value})')
        self.values[key].append((timestamp, value))


    def get(self, key: str, timestamp: int) -> str:
        # we need to look through self.values[key] to find the value time closest to timestamp without
        # going over.
        values = self.values[key]

        # binary search. if the mid time is greater than timestamp, start with the left half.
        left = 0
        right = len(values) - 1
        found = None

        #print(f'get({key}, {timestamp}) initial found={found} left={left} right={right}')
        while right >= left:
            mid = left + (right - left) // 2
            #print(f'  top left={left} right={right} mid={mid}')
            if timestamp < values[mid][0]:
                right = mid - 1
                #print(f'    timestamp {timestamp} is under {values[mid][0]}, taking left side, found={found} left={left} right={right}')
            elif timestamp > values[mid][0]:
                found = mid
                left = mid + 1
                #print(f'    timestamp {timestamp} is over {values[mid][0]}, taking right side, found={found} left={left} right={right}')
            else:
                #print(f'    timestamp is a match, found={found}')
                found = mid
                break
                
        if found is None:
            return ''
        
        #print(f'  returning {values[found][1]}')
        return values[found][1]
            
            
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)


# n = 3

# 1 2 3 4

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.keyValue = {}
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        if not key in self.keyValue:
            self.keyValue[key] = [(timestamp, value)]
        else:
            self.keyValue[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # Start binary search
        history = self.keyValue[key]
        l = 0
        r = len(history) - 1
        while l < r:
            mid = (r + l) // 2
            if timestamp < history[mid][0]:
                r = mid - 1
            elif timestamp > history[mid][0]:
                l = mid + 1
            else:
                return history[mid][1]
        if timestamp < history[l][0]:
            return history[l - 1][1] if l - 1 >= 0 else ''
        return history[l][1] if len(history) > 0 else ''
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.m = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        A = self.m.get(key, None)
        if not A:
            return \"\"
        i = bisect.bisect(A, (timestamp, chr(123)))
        return A[i-1][1] if i else \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kv = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        res = self.kv.get(key, [])
        if len(res) == 0:
            res.append((timestamp, value))
        else:
            index = self.bi_search(timestamp, res, 0, len(res)-1) + 1
            res.insert(index, (timestamp, value))
        self.kv[key] = res
    
    def bi_search(self, t: int, values: List, low: int, hi:int) -> int:
        if low > hi:
            return hi
            
        mid = (hi + low) // 2
        if values[mid][0] == t:
            return mid
        elif t > values[mid][0]:
            return self.bi_search(t, values, mid +1, hi) 
        else:
            return self.bi_search(t, values, low, mid -1)
        

    def get(self, key: str, timestamp: int) -> str:
        res = self.kv.get(key, [])
        if len(res) == 0:
            return \"\"
        else:
            index = self.bi_search(timestamp, res, 0, len(res)-1)
        if index == -1:
            return \"\"
        else:
            return res[index][1]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = collections.defaultdict(list)
        
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append((timestamp, value))
                

    def get(self, key: str, timestamp: int) -> str:
        arr = self.dic[key]
        n = len(arr)
        
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid][0] <= timestamp:
                left = mid + 1
            elif arr[mid][0] > timestamp:
                right = mid - 1
        
        return \"\" if right == -1 else arr[right][1]
        
        
#         arr = self.dic[key]
#         n = len(arr)
        
#         left, right = 0, n - 1
#         while left <= right:
#             mid = (left + right) //2
#             if arr[mid][0] <= timestamp:
#                 left = mid + 1
#             elif arr[mid][0] > timestamp:
#                 right = mid - 1
        
#         return \"\" if left == 0 else arr[left-1][1]
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = defaultdict(list) # key -> (value, timestamp)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        # timestamps are strictly increasing so don't worry about key being in it alreadu
        self.store[key] += [(value, timestamp)]
        

    def get(self, key: str, timestamp: int) -> str:
        # here we can do a binary search to find the greatest timestamp less than timestamp
        if not self.store[key] or timestamp < self.store[key][0][1]:
            return \"\"
        
        # binary search template 1, whilst returning smaller one (r) if we don't find
        lst = self.store[key]
        l, r = 0, len(lst)-1
        while l <= r:
            m = l + (r-l)//2
            if lst[m][1] == timestamp:
                return lst[m][0]
            
            elif timestamp > lst[m][1]:
                l = m + 1
            else:
                r = m - 1
        return lst[r][0]
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((value, timestamp))


    def get(self, key: str, timestamp: int) -> str:
        items = self.store[key]
        if not items: return ''
        
        left = 0
        right = len(items)
        
        while left < right:
            mid = left + (right-left) // 2
            
            val, prevTime = items[mid]
            
            if items[mid][1] <= timestamp:
                left = mid + 1
            elif items[mid][1] > timestamp:
                right = mid
        
            
        
        return \"\" if right == 0 else items[right - 1][0]

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
from bisect import bisect

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kvDict = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.kvDict[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        index = bisect(self.kvDict[key], (timestamp, chr(127)))
        if index == 0:
            return \"\"
        else:
            return self.kvDict[key][index-1][1]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dd = collections.defaultdict(lambda: [[]])

    def set(self, key: str, value: str, timestamp: int) -> None:
        bisect.insort(self.dd[key][0],timestamp)
        self.dd[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dd:
            return ''
        idx = bisect.bisect(self.dd[key][0], timestamp)
        if idx > len(self.dd[key][0]) or idx == 0:
            return ''
        return self.dd[key][idx]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.dict[key]
        low = -1
        high = len(arr) - 1
        while low < high:
            mid = (low + high + 1) // 2
            if arr[mid][0] > timestamp:
                high = mid - 1
            else:
                low = mid
        return arr[low][1] if low > -1 else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.storage = collections.defaultdict(list)
        
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.storage[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        lst = self.storage.get(key, '')
        if not lst or lst is None:
            return ''
        #print(lst)
        # The ascii code range of lower char is [97, 122], thus chr(127) can be used to make sure the located index from bisect.bisect(A, (timestamp, chr(127))) can satisfy the condition: timestamp_prev <= timestamp. In fact, chr(ascii_v) can also be used here where ascii_v's range is [123, 127].
        
        idx = bisect.bisect(lst, (timestamp, chr(127)))
        if not idx or idx is None:
            return ''
        
        return lst[idx-1][1]
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.hash_map = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if not key in self.hash_map:
            self.hash_map[key] = []
        self.hash_map[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        if not key in self.hash_map:
            return \"\"
        if self.hash_map[key][0][-1] > timestamp:
            return \"\"
        value_array = self.hash_map[key]
        index = self.binary_search(timestamp, value_array)
        if value_array[index][-1] > timestamp:
            return value_array[index-1][0]
        else:
            return value_array[index][0]
            
        
        
    def binary_search(self, timestamp, value_array):
        left = 0
        right = len(value_array)-1
        while left < right:
            mid = (left+right)//2
            if value_array[mid][-1] < timestamp:
                left = mid+1
            elif value_array[mid][-1] > timestamp:
                right = mid-1
            else:
                return mid
        return left
            
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
from bisect import bisect

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kvDict = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.kvDict[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.kvDict:
            return \"\"
        index = bisect(self.kvDict[key], (timestamp, chr(127)))
        if index == 0:
            return \"\"
        else:
            return self.kvDict[key][index-1][1]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import bisect

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kw = defaultdict(list)
        self.kt = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        a = self.kw[key]
        
        if len(a) == 0:
            a.append(value)
            self.kt[key].append(timestamp)
        else:
            i = bisect.bisect_right(self.kt[key], timestamp)
            self.kt[key].insert(i, timestamp)
            self.kw[key].insert(i, value)

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect_right(self.kt[key], timestamp)
        
        if i <= 0:
            return \"\"
        
        return self.kw[key][i - 1]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dt = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.dt:
            self.dt[key] = [(timestamp, value)]
        else:
            self.dt[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dt or self.dt[key][0][0] > timestamp:
            return \"\"
        
        values = self.dt[key]
        left, right = 0, len(values)
        while left < right:
            mid = (left + right) // 2
            if values[mid][0] == timestamp:
                return values[mid][1]
            elif values[mid][0] > timestamp:
                right = mid
            else:
                left = mid + 1
        
        return values[right-1][1]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.map = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map.setdefault(key, [])
        self.map[key].append((value, timestamp))

    def binarySearch(self, arr, target, start, end):
        midpoint = (start + end) // 2
        if arr[midpoint][1] == target:
            return arr[midpoint][0]
        
        if arr[midpoint][1] < target:
            if midpoint + 1 > end or arr[midpoint][1] > target:
                return arr[midpoint][0]
            return self.binarySearch(arr, target, midpoint+1, end)
        else:
            return self.binarySearch(arr, target, start, midpoint-1)
        
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.map or timestamp < self.map[key][0][1]:
            return \"\"
            
        return self.binarySearch(self.map[key], timestamp, 0, len(self.map[key])-1)


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.key_value = collections.defaultdict(list)
        self.time_of_key = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        self.key_value[key].append(value)
        self.time_of_key[key].append(timestamp)

    def get(self, key: str, timestamp: int) -> str:
        
        idx = bisect.bisect(self.time_of_key[key], timestamp)
        if idx == 0:
            return ''
        else:
            return self.key_value[key][idx - 1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\" Initialize your data structure here. \"\"\"
        self.TimeMap = defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.TimeMap[key].insert(0, (value, timestamp))
        
    def get(self, key: str, timestamp: int) -> str:
        
        if key in self.TimeMap:
            temp_list = self.TimeMap[key]
            for item in temp_list:
                value, timestamp_prev = item[0], item[1]
                if timestamp_prev <= timestamp:
                    return value
            
            return \"\"

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.hashmap = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.hashmap[key].append((timestamp, value))
        return 

    def get(self, key: str, timestamp: int) -> str:
        index = bisect.bisect(self.hashmap[key], (timestamp, chr(ord(\"z\") + 1)))
        if index != 0:
            return self.hashmap[key][index - 1][1]
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map=collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        self.map[key].append([value,timestamp])
        

    def get(self, key: str, timestamp: int) -> str:
        
        if key not in self.map or self.map[key][0][1]>timestamp:
            
            return \"\"
        
        v=self.map[key]
        
        l, r=0,len(v)
        
        while l<r:
            
            mid=(l+r)//2
            
            if v[mid][1]==timestamp:
                return v[mid][0]
            
            if v[mid][1]>timestamp:
                r=mid
                
            else:
                l=mid+1
        
    
        return v[r-1][0] 
        
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:
    def __init__(self):
        self.dic = collections.defaultdict(list)
        

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

    def get(self, key, timestamp):
        arr = self.dic[key]
        n = len(arr)
        
        left = 0
        right = n-1
        
        while left <= right:
            
            
            mid = int((left + right) / 2)
            if arr[mid][0]== timestamp:
                return arr[mid][1]
            if arr[mid][0] < timestamp:
                left = mid + 1
            elif arr[mid][0] > timestamp:
                right = mid-1
        
        return \"\" if right == -1 else arr[right][1]

        
    
   
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.timeStamp = {}
    
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.timeStamp:
            self.timeStamp[key] = {'values':[],'time':[]}
        self.timeStamp[key]['values'].append(value)
        self.timeStamp[key]['time'].append(timestamp)
        
    def get(self, key: str, timestamp: int) -> str:
        times = self.timeStamp[key]['time']
        
        idx = binarySearch(times,timestamp)
        
        if idx == 0:
            return \"\"
        
        return self.timeStamp[key]['values'][idx-1]


def binarySearch(times,key):
    l = 0
    h = len(times)
    
    while (l<h):
        mid = (l+h)//2
        
        if times[mid]<=key:
            l = mid+1
        elif times[mid]>key:
            h = mid
    
    return h


# def get(self, key, timestamp):
#         arr = self.dic[key]
#         n = len(arr)
        
#         left = 0
#         right = n
        
#         while left < right:
#             mid = (left + right) / 2
#             if arr[mid][0] <= timestamp:
#                 left = mid + 1
#             elif arr[mid][0] > timestamp:
#                 right = mid
        
#         return \"\" if right == 0 else arr[right - 1][1]
        
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.dic:
            self.dic[key].append([timestamp, value])
        else:
            self.dic[key] = [[timestamp, value]]

    def get(self, key: str, timestamp: int) -> str:
        # print(key, timestamp, self.dic)
        if key not in self.dic:
            return ''
        else:
            tmp = self.dic[key]
            l = 0
            r = len(tmp) - 1
            res = -1
            while l <= r:
                m = (l + r) // 2
                if tmp[m][0] == timestamp:
                    res = m
                    break
                elif tmp[m][0] < timestamp:
                    l = m + 1
                else:
                    r = m - 1
            if res < 0:
                if r >= 0:
                    res = r
                else:
                    return ''
                    
            return tmp[res][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        
        10/02: my
        use dict; 
        
        need to bisect to get the timestamp.  binary search. 
        
        like find first version f
        
        value is an object of [value, list of timestamp. ]
        
        because timesteamp are strictly increasing, so it is monolitically increasing.
        
        1 3 5 7 9  f(4)=3
        
        # BUG Forget self.d self!!!
        
        # BUG max_idx=max(l, max_idx)  max_idx cannot be None, > is not supported between instance of none type and int.
        \"\"\"
        self.d = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.d:
            self.d[key].append((timestamp, value))
        else:
            self.d[key] = [(timestamp, value)]
        

    def get(self, key: str, timestamp: int) -> str:
        if key in self.d:
            return self.helper(timestamp, self.d[key])
        else:
            return ''
            
    def helper(self, target, arr):
        # target is the timestamp input
        l,r = 0, len(arr)-1
        max_idx=-1
        while l<=r:
            m = (l+r)//2
            if target==arr[m][0]:
                # there is only 1 timestamp matche due to strictly increasing.
                return arr[m][1]
            # this timestamp is too large, need to find left
            elif arr[m][0]>target:
                r=m-1
            # mid is a valid one! not left! but not sure whether it is the largest
            else:
                l=m+1
                
                max_idx=max(m, max_idx)
        return '' if max_idx==-1 else arr[max_idx][1]  


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeStampOrder :
    def __init__(self, tim, val):
        self.ord_tim = [tim]
        self.tim_dict = {tim:val}

    def insert(self, tim, val):
        self.tim_dict[tim] = val
        i = 0
        while i < len(self.ord_tim):
            if tim > self.ord_tim[i]:
                break
            i+=1
        self.ord_tim.insert(i,tim)

    def get(self, tim):
        i = 0
        while i < len(self.ord_tim):
            if tim >= self.ord_tim[i]:
                return self.tim_dict[self.ord_tim[i]]
            i+=1
        return \"\"
class TimeMap:
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict_key = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.dict_key:
            self.dict_key[key] = TimeStampOrder(timestamp,value)
        else :
            self.dict_key[key].insert(timestamp,value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dict_key:
            return \"\"
        else :
            return self.dict_key[key].get(timestamp)


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import collections
from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.time_map = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.time_map[key].append((timestamp,value))

    def get(self, key: str, timestamp: int) -> str:
        time_map = self.time_map[key]
        left,right = 0, len(time_map)
        
        while left < right:
            mid = left + (right-left) // 2
            if time_map[mid][0] <= timestamp:
                left = mid + 1
            elif time_map[mid][0] > timestamp:
                right = mid
                
        if right != 0:
            return time_map[right-1][1]
        else:
            return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\" Initialize your data structure here. \"\"\"
        self.TimeMap = defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.TimeMap[key].insert(0, (value, timestamp))
        # print(self.TimeMap)
        
    def get(self, key: str, timestamp: int) -> str:
        
        if key in self.TimeMap:
            temp_list = self.TimeMap[key]
            for item in temp_list:
                value, timestamp_prev = item[0], item[1]
                if timestamp_prev <= timestamp:
                    return value
            
            return \"\"

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:
    def __init__(self):
        self.dic = collections.defaultdict(list)
        

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

    def get(self, key, timestamp):
        arr = self.dic[key]
        n = len(arr)
        
        left = 0
        right = n-1
        
        while left <= right:
            
            
            mid = left + (right - left) // 2
            if arr[mid][0]== timestamp:
                return arr[mid][1]
            if arr[mid][0] < timestamp:
                left = mid + 1
            elif arr[mid][0] > timestamp:
                right = mid-1
        
        return \"\" if right == -1 else arr[right][1]

        
    
   
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.M = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        A = self.M.get(key, None)
        if A is None:
            return \"\"
        i = bisect.bisect(A, (timestamp, chr(127)))
        return A[i-1][1] if i else \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        pairs = self.map[key]
        if not pairs or pairs[0][0] > timestamp:
            return \"\"
        start, end = 0, len(pairs) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if pairs[mid][0] <= timestamp:
                start = mid
            else:
                end = mid 
        if pairs[end][0] <= timestamp:
            return pairs[end][1]
        if pairs[start][0] <= timestamp:
            return pairs[start][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = dict() 
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.dic:
            self.dic[key] = []
        self.dic[key].append((timestamp, value))
        
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dic:
            return \"\"
        left = 0
        right = len(self.dic[key])
        mid = None
        while left < right:
            mid = (left + right)//2
            if self.dic[key][mid][0] > timestamp:
                right = mid
            else:
                left = mid + 1
        return \"\" if right==0 else self.dic[key][right-1][1]

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.keyValueStore = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keyValueStore:
            self.keyValueStore[key] = [(-timestamp,value)]
        else:
            bisect.insort(self.keyValueStore[key],(-timestamp,value))
            

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.keyValueStore:
            return \"\"
        else:
            for (nts, val) in self.keyValueStore[key]:
                if -nts<=timestamp:
                    return val
            return \"\"
                    
            
            


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.data = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        if not self.data[key]:
            return \"\"
        left, right = 0, len(self.data[key]) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if timestamp == self.data[key][mid][0]:
                left = mid + 1
            elif timestamp > self.data[key][mid][0]:
                left = mid + 1
            elif timestamp < self.data[key][mid][0]:
                right = mid - 1
        
        if right == -1 or self.data[key][right][0] > timestamp:
            return \"\"
        return self.data[key][right][1]
                
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.hashmap = collections.defaultdict(list) # {Key: [(time, value)]}

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.hashmap[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.hashmap: return \"\"
        
        n = len(self.hashmap[key])
        for i in range(n-1,-1,-1):
            t, v = self.hashmap[key][i]
            if t <= timestamp:
                return v
        return \"\"
            
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

def binarySearch(ls, t):
    n = len(ls)
    if len(ls)==0:
        return ''
    lo = 0
    hi = n-1
    while lo<hi:
        mi = (hi+lo)//2
        if ls[mi][1]==t:
            return ls[mi][0]
        elif ls[mi][1]<t:
            if ls[mi+1][1]>t:
                return ls[mi][0]
            lo = mi+1
        else:
            hi = mi-1
    if ls[hi][1]<=t:
        return ls[hi][0]
    else:
        return ''

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.mp = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.mp[key].append((value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        return binarySearch(self.mp[key], timestamp)


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.M = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        A = self.M.get(key, None)
        if A is None: return \"\"
        i = bisect.bisect(A, (timestamp, chr(127)))
        return A[i-1][1] if i else \"\"


from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        pairList = self.map[key]
        if not pairList:
            return \"\"
        i = bisect.bisect(pairList, (timestamp, chr(255)))        
        
        ## if i == 0: no value at timestamps less than given.
        ## Otherwise, take the value right before
        return pairList[i-1][1] if i else \"\"

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap():

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.timeMap = collections.defaultdict(deque)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
          
        self.timeMap[key].appendleft((value, timestamp))
        
    def get(self, key: str, timestamp: int) -> str:
        
        if key not in self.timeMap:
            return(\"\")
        
        curr = \"\"

        for val, time in self.timeMap[key]:
            
            if time <= timestamp:
                return(val)
                   
        return(curr)

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append( (timestamp, value) )
        

    def get(self, key: str, timestamp: int) -> str:
        if not key in self.d:
            return ''
        
        stack = self.d[key]
        
        idx = bisect.bisect(stack, (timestamp, chr(123)) )
        
        return stack[idx - 1][1] if idx else ''
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

#use binary search  

#List((timestamp: dict))

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        value_lst = self.dic.get(key, None)
        if value_lst is None:
            return ''
        i = bisect.bisect_right(value_lst, (timestamp, chr(127)))
        return value_lst[i-1][1] if i else ''

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        A = self.d.get(key, None)
        if A is None: return \"\"
        i = bisect.bisect(A, (timestamp, chr(127)))
        # print(key, timestamp, A, i)
        return A[i-1][1] if i else \"\"



# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
from bisect import bisect

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kv = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.kv[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.kv:
            return ''
        i = bisect(self.kv[key], (timestamp,'zz')) - 1
        return self.kv[key][i][1] if i >= 0 else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        #group a sequence of key-value pairs into a dictionary of lists
        self.object = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.object[key].append((timestamp,value))
        
        
    def get(self, key: str, timestamp: int) -> str:
        A = self.object.get(key,None)
        if A is None:
            return ''
        i = bisect.bisect(A, (timestamp,chr(255)))
        return A[i-1][1] if i else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:
    from collections import defaultdict
    import bisect
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.timemap = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        sorted_timestamp = self.timemap[key]
        sorted_timestamp.insert( bisect.bisect_right(sorted_timestamp, (timestamp, value)), (timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        sorted_timestamp = self.timemap[key]
        index = bisect.bisect_left(sorted_timestamp, (timestamp, ''))
        if index == len(sorted_timestamp):
            return sorted_timestamp[-1][1]
        elif sorted_timestamp[index][0] == timestamp:
            return sorted_timestamp[index][1]
        elif index == 0 and sorted_timestamp[index][0] != timestamp:
            return ''
        else:
            return sorted_timestamp[index-1][1]

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.myDict = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.myDict[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        arr = self.myDict.get(key, [\"\",\"\"])
        ans = \"\"
        if len(arr) >= 1:
            #only search
            idx = bisect.bisect(arr, [timestamp,chr(ord('z')+1)])
            if idx:
                ans = arr[idx-1][1]
        return ans

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.key = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.key:
            self.key[key] = [[value],[timestamp]]
        else:
            self.key[key][0].append(value)
            self.key[key][1].append(timestamp)
        # print(self.key)

    def get(self, key: str, timestamp: int) -> str:
        value,t = self.key[key]
        low=0
        high=len(t)-1
        while low<high:
            mid = (low+high)//2
            if timestamp < t[high]:
                high = mid - 1
            else:
                low = mid + 1
        if t[low] <= timestamp:
            return value[low]
        else:
            return \"\"
            

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        # https://leetcode.com/problems/time-based-key-value-store/discuss/595719/python-very-simple-98-fast
        self.val_dict = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.val_dict[key].append((value, timestamp))
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.val_dict:
            return \"\"
        val_list  = self.val_dict[key]
        i = len(val_list) -1 
        while i >=0 and val_list[i][1] > timestamp:
            i -= 1
        return val_list[i][0] if i >=0 else \"\"
            


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

#Binary Search (bisect_right) to find item less than or equal to given key 
from bisect import bisect_right
class TimeMap:

    def __init__(self):
        self.keys = dict()
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keys:
            self.keys[key] = []
        
        self.keys[key].append([timestamp, value])
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.keys: return \"\"
        
        values = self.keys[key]
        
        #Or, use [timestamp, chr(127)] to avoid coding binary search
        index = bisect_right(values, [timestamp, chr(127)])
        
        #nothing smaller than or equal to timestamp
        if index == 0: return \"\"
        
        return values[index - 1][1]
    

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.times = collections.defaultdict(list)
        self.values = collections.defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect_right(self.times[key],timestamp)
        return self.values[key][i-1] if i else ''
        
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)


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

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

    def get(self, key, timestamp):
        v = self.d.get(key, [])
        i = bisect.bisect_right(v, [timestamp, chr(ord('z')+1)])
        return v[i-1][1] if i else ''

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.data = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return ''
        l = self.data[key]
        i = bisect.bisect(l, [timestamp + 1])
        if i == 0:
            return ''
        return l[i - 1][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.dict[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 arr[right - 1][1] if right > 0 else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append([timestamp, value])
        
        

    def get(self, key: str, timestamp: int) -> str:
        elements = self.dic.get(key, None)
        if not elements:
            return \"\"
        i = bisect.bisect(elements, [timestamp, chr(200)])
        return elements[i-1][1] if i else \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import bisect
from collections import defaultdict
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.tkv = defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.tkv:
            self.tkv[key][0].append(timestamp)
            self.tkv[key][1].append(value)
        else:
            self.tkv[key] = [[timestamp],[value]]

    def get(self, key: str, timestamp: int) -> str:
        get_index = bisect.bisect_left(self.tkv[key][0], timestamp)
        n = len(self.tkv[key][0])
            
        if get_index > n - 1:
                return self.tkv[key][1][n - 1]
        else: 
            if self.tkv[key][0][get_index] == timestamp:
                return self.tkv[key][1][get_index]
            elif get_index > 0:
                return self.tkv[key][1][get_index - 1]
            else:
                return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.M = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        A = self.M.get(key, None)
        if A is None: return \"\"
        i = bisect.bisect(A, (timestamp, chr(127)))
        return A[i-1][1] if i else \"\"

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        from collections import defaultdict
        self.kv = defaultdict(list)
        z=0

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.kv[key].append((timestamp, value))
        z=0

    def get(self, key: str, timestamp: int) -> str:
        from bisect import bisect_right
        if key not in self.kv:
            return \"\"
        
        ind = bisect_right(self.kv[key], (timestamp+0.1,\"\"))-1  #  +0.1 to resolve the case when timestamp == timestamp_prev
        if ind == -1:
            return \"\"
        else:
            return self.kv[key][ind][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

#hash, list, binary search
#Runtime: 6308 ms, faster than 5.05%
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((timestamp, value))

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


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import bisect
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.time_map = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.time_map[key].append((timestamp, value))
            
    def get(self, key: str, timestamp: int) -> str:
        value_list = self.time_map.get(key, None)
        if not value_list:
            return \"\"
        left, right = 0, len(value_list) - 1
        while left < right:
            mid = (left + right + 1) // 2
            pre_time, value = value_list[mid]
            if pre_time > timestamp:
                right = mid - 1
            else:
                left = mid
        return value_list[left][1] if value_list[left][0] <= timestamp else ''
        
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = defaultdict(list) 

    def set(self, key: str, value: str, timestamp: int) -> None:
        # find key and check, set new key if it doesn't exist
        self.dict[key].append((value, timestamp))
            
    def get(self, key: str, timestamp: int) -> str:
        arr = self.dict[key]
        n = len(arr)
        
        left = 0
        right = n
        
        # Short answer
        # v = self.d.get(key, [])
        # i = bisect.bisect_right(v, [timestamp, chr(ord('z')+1)])
        # return v[i-1][1] if i else ''
        
        while left < right:
            mid = (left + right) // 2 
            if arr[mid][1] <= timestamp:
                left = mid + 1
            elif arr[mid][1] > timestamp:
                right = mid
        
        return \"\" if right == 0 else arr[right - 1][0]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.times = collections.defaultdict(list)
        self.values = collections.defaultdict(list)        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)        

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect(self.times[key], timestamp)
        return self.values[key][i - 1] if i else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.keys = collections.defaultdict(list)
        self.times = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.keys[key].append(value)
        self.times[key].append(timestamp)
        
        
    def get(self, key: str, timestamp: int) -> str:
        times = self.times[key]
        
        l, r = 0, len(times)
        while l < r:
            mid = l + (r - l ) // 2
            if timestamp >= times[mid]:
                l = mid + 1
            else:
                r = mid
        return self.keys[key][l-1] if l != 0 else ''
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap(object):

    def __init__(self):
        self.dic = collections.defaultdict(list)
        

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

    def get(self, key, timestamp):
        arr = self.dic[key]
        n = len(arr)
        
        left = 0
        right = n
        
        while left < right:
            mid = (left + right) // 2
            if arr[mid][0] <= timestamp:
                left = mid + 1
            elif arr[mid][0] > timestamp:
                right = mid
        
        return \"\" if right == 0 else arr[right - 1][1]

class TimeMap:

    def __init__(self):
        self.store = defaultdict(list)
    

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.store.get(key)
        if arr is None:
            return \"\"
        l = 0
        r = len(arr) - 1
        result = \"\"
        while l <= r:
            mid = (l + r) // 2
            if arr[mid][0] <= timestamp:
                result = arr[mid][1]
                l = mid + 1
            else:
                r = mid - 1
        return result
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = defaultdict(list) 

    def set(self, key: str, value: str, timestamp: int) -> None:
        # find key and check, set new key if it doesn't exist
        self.dict[key].append((value, timestamp))
            
    def get(self, key: str, timestamp: int) -> str:
        arr = self.dict[key]
        n = len(arr)
        
        left = 0
        right = n
        
        while left < right:
            mid = (left + right) // 2 
            if arr[mid][1] <= timestamp:
                left = mid + 1
            elif arr[mid][1] > timestamp:
                right = mid
        
        return \"\" if right == 0 else arr[right - 1][0]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        res = self.map[key]
        if not res:
            return \"\"
       
        return self.findFirstSmaller(res, timestamp)
       
    
    def findFirstSmaller(self, nums, target):
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left+right)//2
            if nums[mid][0] < target:
                left = mid
            elif nums[mid][0] == target:
                right = mid
            else:
                right = mid
        if nums[right][0] <= target:
            return nums[right][1]
        if nums[left][0] <= target:
            return nums[left][1]
        return \"\"
        
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.timeMap = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.timeMap:
            self.timeMap[key] = []
        self.timeMap[key].append([timestamp, value])        

    def get(self, key: str, timestamp: int) -> str:
        values = self.timeMap[key]
        
        left = 0
        right = len(values)
        
        while left < right:
            mid = (left + right) // 2
            if values[mid][0] <= timestamp:
                left = mid + 1
            elif values[mid][0] > timestamp:
                right = mid
        
        return \"\" if right == 0 else values[right - 1][1]



import collections
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.storage = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.storage[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        arr = self.storage.get(key)
        
        lft, rht = 0, len(arr)
        while lft < rht:
            mid = lft + (rht - lft) // 2
            if arr[mid][0] <= timestamp:
                lft = mid + 1
            else:
                rht = mid
        
        return arr[lft - 1][1] if lft != 0 else ''
        
        
#         if not arr:
#             return \"\"
#         if arr[0][0] > timestamp:
#             return \"\"
       
#         lft, rht = 0, len(arr) - 1
#         while lft <= rht:
#             mid = lft + (rht - lft) // 2
#             if arr[mid][0] == timestamp:
#                 return arr[mid][1]
#             if arr[mid][0] < timestamp:
#                 lft = mid + 1
#             else:
#                 rht = mid - 1
#         return arr[rht][1]
        

from collections import defaultdict
from bisect import bisect_left
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.mapping = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.mapping[key].append((timestamp, value))
        
        
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.mapping:
            return \"\"
        
        ts = self.mapping[key]
        start, end = 0, len(ts) - 1 
        
        while start + 1 < end:
            mid = (start + end) // 2
            midVal, _ = ts[mid]
            if midVal <= timestamp:
                start = mid 
            else:
                end = mid 
                
        if ts[end][0] <= timestamp:
            return ts[end][1]
        if ts[start][0] <= timestamp:
            return ts[start][1]
        
        return \"\"
            
        
            
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.storage = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.storage[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.storage:
            return \"\"
        
        returned = self.storage[key]
        l = 0
        r = len(returned)
        
        while l < r:
            mid = l + (r - l) // 2
            
            if returned[mid][1] <= timestamp:
                l = mid + 1
            elif returned[mid][1] > timestamp:
                r = mid
                
        # r - 1 because we found the spot where timestamp < returned[mid], so 
        # we wanna grab the proper index
        return \"\" if r == 0 else returned[r - 1][0]
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.storage = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.storage[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.storage:
            return \"\"
        
        returned = self.storage[key]
        l = 0
        r = len(returned)
        
        while l < r:
            mid = l + (r - l) // 2
            
            if returned[mid][1] <= timestamp:
                l = mid + 1
            elif returned[mid][1] > timestamp:
                r = mid
                
        return \"\" if r == 0 else returned[r - 1][0]
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.data = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append((timestamp, value))
        
    def binarySearch(self, l, target):
        low = 0
        high = len(l) - 1
        while low <= high:
            mid = (low + high) // 2
            if l[mid][0] <= target < l[mid + 1][0]:
                return mid
            elif l[mid][0] > target:
                high = mid - 1
            else:
                low = mid + 1
        return -1
        
    def get(self, key: str, timestamp: int) -> str:
        
        if key not in self.data or timestamp < self.data[key][0][0]:
            return \"\"
    
        if self.data[key][-1][0] <= timestamp:
            return self.data[key][-1][1]

        return self.data[key][self.binarySearch(self.data[key], timestamp)][1]

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.d:
            self.d[key] = [(timestamp, value)]
        else:
            self.d[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d:
            return ''
        
        # Binary search
        arr = self.d[key]
        left = 0
        right = len(arr) - 1

        while left <= right:
            mid = (left + right) // 2

            if arr[mid][0] == timestamp:
                return arr[mid][1]
            elif arr[mid][0] < timestamp:
                left = mid + 1
            else:
                right = mid - 1

        return '' if right == -1 else arr[right][1]
                


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.hashmap = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.hashmap[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        l = self.hashmap[key]
        
        left = 0
        right = len(l)-1 
        
        if l[0][1] > timestamp:
            return \"\"
        
        while left <= right:
            mid = left + (right-left) // 2 
            if l[mid][1] <= timestamp:
                left = mid+1 
            else:
                right = mid-1
        return l[right][0]

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

# to store key-value pairs, use a dic. But a key has different values bases on the timestamp. We need something to store the values as well as the timestamp. We can use a queue(or deque)
# because set is in chronological order, time for set is O(1). But for get we need to use binary serach to search the nearest element, so it's O(logn). space is O(n) 
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = collections.defaultdict(list)
    def search(self,pairs,time):
        l,r = 0,len(pairs)
        while l<r:
            mid = (l+r)//2
            if pairs[mid][0]>time:
                r = mid
            else:
                l = mid+1
        return l
    
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append([timestamp,value])

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dic or self.dic[key][0][0]>timestamp:
            return ''
        List = self.dic[key]
        index = self.search(List,timestamp)
        return List[index-1][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        sorted_values = self.store.get(key, None)
        if sorted_values is None: return \"\"
        value = self.bisect_with_timestamp(0, len(sorted_values) - 1, sorted_values, timestamp)
        return value
        
    def bisect_with_timestamp(self, left, right, values, timestamp):
        while left <= right:
            pivot = (left + right) // 2
            pivot_stamp, pivot_value = values[pivot]
            if pivot_stamp == timestamp:
                return pivot_value
            else:
                if pivot_stamp < timestamp:
                    left = pivot + 1
                else:
                    right = pivot - 1
                    
        pivot_stamp, pivot_value = values[pivot]
        if pivot_stamp < timestamp:
            return pivot_value
        else:
            if pivot - 1 >= 0:
                pivot_stamp, pivot_value = values[pivot - 1]
                return pivot_value
            else:
                return \"\"
                
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.hash = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.hash:
            self.hash[key] = {'times':[],'values':[]}
        self.hash[key]['values'].append(value)
        self.hash[key]['times'].append(timestamp)
        
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.hash:
            return \"\"
        
        values = self.hash[key]['times']
        idx = search(timestamp,self.hash[key]['times'])
        # print(\"This is the key:\",key)
        # print(\"This is the values:\",self.hash[key]['values'])
        # print(\"This is times:\",values)
        # print(\"This is timestamp:\",timestamp)
        # print(\"This is idx:\",idx)
        # print(\"*******************\")
        if idx is not None:
            return self.hash[key]['values'][idx]
        return \"\"
        
        
def search(target,values):
    l = 0
    r = len(values)-1
    ans = None
    
    while l<=r:
        mid = (l+r)//2
        
        if values[mid]==target:
            return mid
        
        if values[mid]>target:
            r = mid-1
        
        if values[mid]<target:
            ans = mid
            l = mid+1
    
    return ans
        
    
    

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.store = defaultdict(list)
    

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.store.get(key)
        if arr is None:
            return \"\"
        l = 0
        r = len(arr) - 1
        result = \"\"
        while l <= r:
            mid = l + (r - l) // 2
            if arr[mid][0] <= timestamp:
                result = arr[mid][1]
                l = mid + 1
            else:
                r = mid - 1
        return result
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

import collections
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.storage = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.storage[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        arr = self.storage.get(key)
        if not arr:
            return \"\"
        if arr[0][0] > timestamp:
            return \"\"
       
        lft, rht = 0, len(arr) - 1
        while lft <= rht:
            mid = lft + (rht - lft) // 2
            if arr[mid][0] == timestamp:
                return arr[mid][1]
            if arr[mid][0] < timestamp:
                lft = mid + 1
            else:
                rht = mid - 1
        return arr[rht][1]
        

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((value,timestamp))

    def get(self, key: str, timestamp: int) -> str:
        if not self.d[key]:
            return \"\"
        if len(self.d[key]) == 1:
            if self.d[key][0][1] <= timestamp:
                return self.d[key][0][0]
            else:
                return \"\"
        
        i=0
        j=len(self.d[key])-1
        while i<=j:
            m=i + ((j-i)//2)
            if self.d[key][m][1]<timestamp:
                i=m+1
            elif self.d[key][m][1]>timestamp:
                j=m-1
            elif self.d[key][m][1]==timestamp:
                return self.d[key][m][0]
            else:
                pass
        if j!=-1:
            return self.d[key][j][0]
        else:
            return \"\"
            
            


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self.M = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.M[key].append((timestamp, value))
        

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


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)


class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.t_ = collections.defaultdict(list)
        self.v_ = collections.defaultdict(list)
        self.max_ = collections.defaultdict(int)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.t_[key].append(timestamp)
        self.v_[key].append(value)
        self.max_[key] = max(self.max_[key], timestamp)
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.t_:
            return \"\"
        if timestamp >= self.max_[key] :
            return self.v_[key][-1]
        # 返回index 的右手邊的數值
        v = bisect.bisect_right(self.t_[key], timestamp)
        if v :
            return self.v_[key][v-1]
        return \"\"
        

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        all_values = self.dic[key]
        if not all_values:
            return \"\"
        val_index = -1
        for i in range(len(all_values)-1, -1, -1):
            if all_values[i][0] <= timestamp:
                val_index = i
                break
        return all_values[val_index][1] if val_index > -1 else \"\"
            
                
    

from collections import defaultdict
import bisect
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.cache = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.cache[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.cache:
            return -1
        
        tsVals = self.cache[key]
        idx = self.binarySearch(tsVals, timestamp)
        #idx = bisect.bisect_left(tsVals, (timestamp, chr(127)))
        
        return tsVals[idx][1] if idx >= 0 else \"\"
    
    def binarySearch(self, tsVals, timestamp):
        low = 0
        high = len(tsVals)
        
        while low < high:
            mid = low + ((high -low)//2)
            
            if tsVals[mid][0] == timestamp:
                return mid 
            
            if tsVals[mid][0] < timestamp:
                low = mid + 1
            else:
                high = mid
        
        #[foor] [1,bar][4, bar2]        
        return low - 1
    
#         def __init__(self):
#         self.M = collections.defaultdict(list)

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

#     def get(self, key, timestamp):
#         A = self.M.get(key, None)
#         if A is None: return \"\"
#         i = bisect.bisect_left(A, (timestamp, chr(127)))
#         return A[i-1][1] if i else \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

\"\"\"
[\"TimeMap\",\"set\",\"set\",\"get\",\"get\",\"get\",\"get\",\"get\"]
[[],[\"love\",\"high\",10],[\"love\",\"low\",20],[\"love\",5],[\"love\",10],[\"love\",15],[\"love\",20],[\"love\",25]]


return [null,null,null,\"\",\"high\",\"high\",\"low\",\"low\"]
\"\"\"
class TimeMap:

    def __init__(self):
        self.t = {}
        self.d = collections.defaultdict(list)
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((value, timestamp))
        if (key, value) not in self.t:
            self.t[(key, value)] = (timestamp, timestamp)
        else:
            self.t[(key, value)] = (self.t[(key, value)][0], timestamp)
        

    def get(self, key: str, timestamp: int) -> str:
        # print(self.t, self.d)
        values = self.d[key]
        n = len(values)
        l, r = 0, n - 1
        while l < r:
            m = (l + r) // 2
            if values[m][1] == timestamp:
                return values[m][0]
            if values[m][1] < timestamp:
                l = m + 1
            else:
                r = m
        # print(l)
        if values[l][1] == timestamp:
            return values[l][0]
        if l > 0 and values[l][1] > timestamp and values[l - 1][1] < timestamp:
            return values[l - 1][0]
        if values[l][1] > timestamp < values[0][1]:
            return ''
        return values[-1][0]
                


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from typing import Dict, List
from math import floor

class TimeMap:

    def __init__(self):
        self.data: Dict[str, List[(int, str)]] = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.data:
            self.data[key] = []
        self.data[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return \"\"

        values = self.data[key]
        start = 0
        end = len(values)

        while start < end:
            mid = floor((start + end) / 2)
            mid_timestamp, mid_value = values[mid]

            if timestamp == mid_timestamp:
                return mid_value
            elif timestamp < mid_timestamp:
                end = mid
            else:
                start = mid + 1

        largest_index_less_than = start - 1
        if largest_index_less_than < 0:
            return \"\"

        _, value = values[largest_index_less_than]
        return value

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.times = defaultdict(list)
        self.values = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)
        
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.times:
            return \"\"
        low = 0
        high = len(self.times[key])
        while low < high:
            mid = high + (low - high) // 2
            if timestamp < self.times[key][mid]:
                high = mid
            elif timestamp > self.times[key][mid]:
                low = mid + 1
            else:
                return self.values[key][mid]
        if high == 0:
            return \"\"
        return self.values[key][low - 1]



# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((value, timestamp))
        

    def get(self, key: str, timestamp: int) -> str:
        # next((v for v,t in reversed(self.d[key]) if t <= timestamp), \"\")
        return self.bsearch(self.d[key], timestamp)
    
    def bsearch(self, l, time):
        if not l:
            return \"\"

        lo, hi = 0, len(l)-1
        while lo <= hi:
            mid = (hi+lo)//2
            v, t = l[mid]
            if t <= time:
                lo = mid + 1 
            else:
                hi = mid - 1
                
        return l[hi][0] if l[hi][1] <= time else \"\"
            
            
            
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.kvStore = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.kvStore[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key in self.kvStore:
            values = self.kvStore[key]
            left, right = 0, len(values) - 1

            while left <= right:
                if left == right:
                    return values[left][1]
                
                mid = (left + right) // 2
                midTS, midValue = values[mid]
                
                if midTS == timestamp:
                    return midValue
                elif midTS > timestamp:
                    right = mid - 1
                elif left + 1 <= right and values[left + 1][0] <= timestamp:
                    left = mid + 1
                else:
                    return midValue
                    
        return \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.data = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data or timestamp < self.data[key][0][1]:
            return ''
        low = 0
        high = len(self.data[key])
        while low < high:
            mid = (low + high) // 2
            if self.data[key][mid][1] < timestamp + 1:
                low = mid + 1
            else:
                high = mid
        return self.data[key][low - 1][0]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        #print(timestamp)
        if key in self.map:
            low = 0
            high = len(self.map[key])-1
            while low <= high:
                middle = (low + high)//2
                if self.map[key][middle][0] == timestamp:
                    return self.map[key][middle][1]
                elif self.map[key][middle][0] < timestamp:
                    low = middle + 1
                else:
                    high = middle - 1
                
            if self.map[key][middle][0] > timestamp:
                if middle > 0: 
                    return self.map[key][middle-1][1]
            else:
                    return self.map[key][middle][1]
                
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict
class TimeMap:
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        arr = self.map[key]
        left = 0
        right = len(arr) - 1
        if arr[left][0] > timestamp:
            return \"\"
        elif arr[right][0] <= timestamp:
            return arr[right][1]
        else:
            # Binary search
            while left <= right:
                mid = (left + right) // 2
                if arr[mid][0] == timestamp:
                    return arr[mid][1]
                elif arr[mid][0] < timestamp:
                    left = mid + 1
                else:
                    right = mid - 1
            return arr[right][1]

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        from collections import defaultdict
        import bisect
        # Key value pairs of (keys, list of (timestamp, value) tuples)
        # Binary search to find the value in O(log n) time
        self._store = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self._store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if not self._store[key]:
            return \"\"
        idx = self.bsearch(self._store[key], timestamp)
        if self._store[key][idx][0] > timestamp and idx - 1 >= 0:
            idx -= 1
        temp = self._store[key][idx]
        return temp[1] if temp[0] <= timestamp else \"\"
    
    def bsearch(self, arr, timestamp):
        lo = 0
        hi = len(arr) - 1
        
        while lo < hi:
            mid = (lo + hi)//2
            if arr[mid][0] < timestamp:
                lo = mid + 1
            else:
                hi = mid
        return lo


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.__hash_map={}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.__hash_map:
            self.__hash_map[key].append((timestamp,value))
        else:
            self.__hash_map[key]=[(timestamp,value)]

    def get(self, key: str, timestamp: int) -> str:
        if key in self.__hash_map:
            arr=self.__hash_map[key]
            # arr.sort(key=lambda x:x[0])
            list_size=len(arr)
            l=0
            r=list_size-1
            while l<=r:
                mid=l+(r-l)//2
                if arr[mid][0]==timestamp:
                    return arr[mid][1]
                elif arr[mid][0]<timestamp:
                    l=mid+1
                else:
                    r=mid-1
                    #[8]   t=2
            if r< 0:
                return \"\"
            else:
                return arr[r][1]
        else:
            return \"\"

        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
\"\"\"
[k,1][k,5][k,8][,1][,1]

\"\"\"

class TimeMap:

    def __init__(self):
        self.timeMap = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.timeMap:
            self.timeMap[key] = []
        self.timeMap[key].append([timestamp, value])        

    def get(self, key: str, timestamp: int) -> str:
        values = self.timeMap[key]
        
        left = 0
        right = len(values)-1
        while left <= right:
            mid = (left + right) // 2
            if values[mid][0] == timestamp:
                return values[mid][1]
            elif values[mid][0] < timestamp:
                left = mid + 1
            elif values[mid][0] > timestamp:
                right = mid - 1
        print(values[right][0], timestamp)
        if values[right][0] < timestamp:
            return values[right][1]
        else:
            return \"\"




class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        from collections import defaultdict
        self.mp = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.mp[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        l, h = 0, len(self.mp[key])-1
        
        while l <= h:
            mid = (l+h)//2
            if self.mp[key][mid][0] == timestamp:
                return self.mp[key][mid][1]
            elif self.mp[key][mid][0] < timestamp:
                l = mid + 1
            else:
                h = mid - 1
        if h == -1:
            return ''
        else:
            return self.mp[key][h][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        pair = (timestamp, value)
        self.map[key].append(pair)

    def get(self, key: str, timestamp: int) -> str:
        def binarysearch(arr, l, r):
            if l >= r:
                if arr[l][0] > timestamp:
                    return arr[max(l-1, 0)]
                return arr[l]
            mid = (l + r) // 2
            if arr[mid][0] < timestamp:
                return binarysearch(arr, mid+1, r)
            else:
                return binarysearch(arr, l, mid-1)

        if key in self.map:
            arr = self.map[key]
            if len(arr) == 0:
                return \"\"
            pair = binarysearch(arr, 0, len(arr)-1)
            if arr[0][0] > timestamp: 
                return \"\"
            else:
                return pair[1]
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        self.dic[key].append([timestamp,value])
        
    def get(self, key: str, timestamp: int) -> str:
        
        left = 0
        right = len(self.dic[key]) - 1
        
        if self.dic[key][left][0] > timestamp:
            return ''
        while left < right:
            mid = left + (right-left+1) // 2
            if self.dic[key][mid][0] > timestamp:
                right = mid - 1
            else:
                left = mid
                
        return self.dic[key][left][1]
        
        
        
        
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class Node:
    def __init__(self,time,val):
        self.left = None
        self.right = None
        self.time = time
        self.val = val
        

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dic = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append((timestamp,value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dic.keys(): return \"\"
        
        l, r = 0, len(self.dic[key])-1
        
        while l+1 < r:
            mid = (l + r) // 2
                
            if self.dic[key][mid][0] == timestamp:
                return self.dic[key][mid][1]
            elif self.dic[key][mid][0] < timestamp:
                l = mid
            else:
                r = mid
                
        if self.dic[key][r][0] <= timestamp:
            return self.dic[key][r][1]
        if self.dic[key][l][0] <= timestamp:
            return self.dic[key][l][1]
        
        return \"\"

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from bisect import *
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d= {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.d:
            self.d[key] = [(timestamp, value)]
        else:
            self.d[key].append((timestamp,value))
    
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d: return \"\"
        #print (key, tm)
        l, r = 0, len(self.d[key])-1
        
        while l+1<r:
            m = l + (r-l)//2
            if self.d[key][m][0] == timestamp: return self.d[key][m][1]
            if self.d[key][m][0] < timestamp: 
                l = m 
            else: r = m - 1 
        if self.d[key][r][0] <= timestamp: return self.d[key][r][1]
        if self.d[key][l][0] <= timestamp: return self.d[key][l][1]
        # no value with smaller timestamp
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import defaultdict

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.data = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append({
            \"value\": value,
            \"timestamp\": timestamp
        })

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return \"\"

        data = self.data[key]
        n = len(data)

        result = \"\"
        start, end = 0, n - 1
        
        while start <= end:
            mid = start + (end - start) // 2
            
            if data[mid][\"timestamp\"] > timestamp:
                end = mid - 1
            elif data[mid][\"timestamp\"] < timestamp:
                start = mid + 1
                result = data[mid][\"value\"]
            else:
                return data[mid][\"value\"]
            
        return result


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.t_ = collections.defaultdict(list)
        self.v_ = collections.defaultdict(list)
        self.max_ = collections.defaultdict(int)
        

    def set(self, key, value, timestamp):
        \"\"\"
        :type key: str
        :type value: str
        :type timestamp: int
        :rtype: None
        \"\"\"
        self.t_[key].append(timestamp)
        
        self.v_[key].append(value)
        
        self.max_[key] = max(self.max_[key], timestamp)
        

    def get(self, key, timestamp):
        \"\"\"
        :type key: str
        :type timestamp: int
        :rtype: str
        \"\"\"
        if key not in self.t_:
            return \"\"
        if timestamp >= self.max_[key]:
            return self.v_[key][-1]
        v = bisect.bisect_right(self.t_[key], timestamp)
        #print(\"v :\",v)
        if v:
            #print(\"self.v_[key][v - 1] :\",self.v_[key][v - 1])
            return self.v_[key][v - 1]
        return \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.key_map = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if not self.key_map.get(key):
            self.key_map[key] = []
        self.key_map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        val = \"\"
        timestamp_list = self.key_map.get(key)
        if timestamp_list:
            index = bisect.bisect(timestamp_list, (timestamp,chr(127)))
            if index:
                val = timestamp_list[index-1][1]
        return val


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from collections import deque
class TimeMap:

    def bs(self, target, seq):
        low = 0
        high = len(seq) - 1
        result = ''
        foundTs = -1
        while(low <= high):
            mid = (low + high) // 2
            ts = seq[mid][0]
            if ts <= target:
                if ts == target:
                    return seq[mid][1]
                elif ts > foundTs:
                    foundTs = ts
                    result = seq[mid][1]
                low = mid + 1
            else:
                high = mid - 1
        return result
                
    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.map = {}    

    def set(self, key: str, value: str, timestamp: int) -> None:
        if not key in self.map:
            self.map[key] = [(timestamp, value)]
        else:
            self.map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if not key in self.map:
            return ''
        return self.bs(timestamp, self.map[key])


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from heapq import heappop, heappush
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.res={}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.res:
            self.res[key]=[]
            self.res[key]=[[value,timestamp]]
        else:
             self.res[key].append([value,timestamp])

    def get(self, key: str, timestamp: int) -> str:
        array=self.res[key]
        n = len(self.res[key])
        i = 0
        j =n-1
        if array[i][1]>timestamp:
            return \"\"
        while i<=j:
            mid = i+(j-i)//2
            if array[mid][1]==timestamp:
                return array[mid][0]
            elif array[mid][1]<timestamp:
                i = mid+1
            else:
                j = mid-1
        return array[j][0]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        self._data = collections.defaultdict(list)
        
    def set(self, key, value, timestamp):
        self._data[key].append((value, timestamp))

    def get(self, key, timestamp):
        if key not in self._data:
            return ''
        
        # 找数组里最后一个小于给定的timestamp的数据
        arr = self._data[key]
        start, end = 0, len(arr) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if arr[mid][1] <= timestamp:
                start = mid
            else:
                end = mid - 1
        
        if arr[end][1] <= timestamp:
            return arr[end][0]
        if arr[start][1] <= timestamp:
            return arr[start][0]
        
        return ''

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = {}
    
    def search_time(self,values, time, start, end):
        n = len(values)
        index = int((start + end) / 2)
        if (end - start) <= 20:
            cur = end
            while cur >= start:
                if values[cur][1] <= time:
                    return values[cur][0]
                cur -= 1
            return \"\"
                
        if values[index][1] == time:
            return values[index][0]
        elif values[index][1] < time:
            start = index
        else:
            end = index
        return self.search_time(values, time, start, end)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.store:
            self.store[key].append((value, timestamp))
        else:
            self.store[key] = [(value, timestamp)]

    def get(self, key: str, timestamp: int) -> str:
        if key in self.store:
            values = self.store[key]
            return self.search_time(values, timestamp, 0, len(values)-1)
        else:
            return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.memo = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.memo[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if self.memo.get(key, None):
            lst = self.memo[key]

            left = 0
            right = len(lst) - 1
            while left <= right:
                mid = (left + right) // 2
                if lst[mid][0] <= timestamp and (mid == len(lst) - 1 or lst[mid+1][0] > timestamp):
                    return lst[mid][1]
                elif lst[mid][0] > timestamp:
                    right = mid -1
                elif lst[mid+1][0] <= timestamp:
                    left = mid + 1
            return \"\"
        else:
            return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict1 = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict1[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        A = self.dict1.get(key, None)
        
        if A is None: return \"\"
        
        i = bisect.bisect(A, (timestamp, chr(127)))
        return A[i-1][1] if i else \"\"
        
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        
        \"\"\"
        self.dic = {}
        
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.dic:
            self.dic[key] = [[value, timestamp]]
        else:
            self.dic[key].append([value, timestamp])
        

    def get(self, key: str, timestamp: int) -> str:
        
        if key not in self.dic or len(self.dic[key]) == 0:
            return \"\"
        
        n = len(self.dic[key])
        
        l = 0
        r = n - 1
        
        while l < r:
            mid = l + (r - l + 1)//2
            if self.dic[key][mid][1] > timestamp:
                r = mid - 1
            elif self.dic[key][mid][1] == timestamp:
                return self.dic[key][mid][0]
            else:
                l = mid
                
        if self.dic[key][l][1] <= timestamp:
            return self.dic[key][l][0]
        else:
            return \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

from bisect import *
class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.d= {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.d:
            self.d[key] = [(timestamp, value)]
        else:
            insort(self.d[key], (timestamp,value))
    
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d: return \"\"
        #print (key, tm)
        l, r = 0, len(self.d[key])-1
        
        while l+1<r:
            m = l + (r-l)//2
            if self.d[key][m][0] == timestamp: return self.d[key][m][1]
            if self.d[key][m][0] < timestamp: 
                l = m 
            else: r = m - 1 
        if self.d[key][r][0] <= timestamp: return self.d[key][r][1]
        if self.d[key][l][0] <= timestamp: return self.d[key][l][1]
        # no value with smaller timestamp
        return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.dict = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        
        left = 0
        right = len(self.dict[key])
        
        while left < right:
            mid = (left+right)//2
            
            if self.dict[key][mid][0] == timestamp:
                return self.dict[key][mid][1]
            elif self.dict[key][mid][0] <= timestamp:
                left = mid + 1
            else:
                right = mid
            
        return \"\" if right == 0 else self.dict[key][right-1][1]
                
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

# 10:45 - 11:30
from collections import defaultdict
from bisect import bisect_right

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.values = defaultdict(list)
        self.timestamps = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.values[key].append(value)
        self.timestamps[key].append(timestamp)
        

    def get(self, key: str, timestamp: int) -> str:
        ts = self.timestamps[key]
        index = bisect_right(ts, timestamp)
        if index == 0:
            return ''
        return self.values[key][index - 1]
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.TimeMaps=collections.defaultdict(list)
        
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        self.TimeMaps[key].append((timestamp,value))
        

#     # binary search with repeated values    
#     def get(self, key: str, timestamp: int) -> str:
        
#         # get all the values with the same key
#         arr=self.TimeMaps[key]

#         if not arr: return ''
        
#         # sort by timestamp
#         arr.sort(key=lambda x: x[0])
 
#         l=0
#         r=len(arr)-1
#         res=-1
#         while l<=r:
            
#             m=l+(r-l)//2
            
#             if arr[m][0]==timestamp:
#                 return arr[m][1]
            
#             if arr[m][0]>timestamp:
#                 r=m-1
#             else:
#                 res=m
#                 l=m+1

#         return arr[res][1] if res !=-1 else ''


    def get(self, key: str, timestamp: int) -> str:
        if key not in self.TimeMaps:
            return ''
        return self.b_search(self.TimeMaps[key], timestamp)

    def b_search(self, lst, target):
        left, right = 0, len(lst) - 1
        res = ''
        while left <= right:
            mid = left + (right - left) // 2
            item = lst[mid]
            if item[0] == target:
                return item[1]
            if item[0] > target:
                right = mid - 1
            else:
                left = mid + 1
                res = item[1]
        return res
        


class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.key_map = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if not self.key_map.get(key):
            self.key_map[key] = []
        self.key_map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        val = \"\"
        timestamp_list = self.key_map.get(key)
        if timestamp_list:
            index = bisect.bisect(timestamp_list, (timestamp,))
            # print (timestamp, index)
            # print (timestamp_list)
            if index > len(timestamp_list) - 1:
                index -= 1
            
            if timestamp_list[index][0] > timestamp:
                index -= 1

            if index >= 0:
                val = timestamp_list[index][1]
        return val


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        
        if key not in self.store:
            self.store[key] = [(timestamp, value)]
        else:
            self.store[key].append((timestamp, value))


    def get(self, key: str, timestamp: int) -> str:
        # print(self.store, timestamp)
        
        if key not in self.store:
            return \"\"
        i = bisect.bisect(self.store[key],( timestamp, chr(127)))
        return self.store[key][i-1][1] if i else \"\"
        


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.data = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.data:
            self.data[key].append((value, timestamp))
        else:
            self.data[key] = [(value, timestamp)]

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data: return \"\"  
        lo = 0
        hi = len(self.data[key])
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if self.data[key][mid][1] == timestamp:
                return self.data[key][mid][0]
            elif self.data[key][mid][1] < timestamp:
                lo = mid + 1
            else: 
                hi = mid
        
        if lo == 0 and self.data[key][lo][1] > timestamp:
            return \"\"
        return self.data[key][lo-1][0]
        
        


class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.mapping = collections.defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        lists = self.mapping[key]
        if not lists:
            self.mapping[key] = [(timestamp, value)]
            return
        start, end = 0, len(lists) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if lists[mid][0] == timestamp:
                self.mapping[key][mid] = (timestamp, value)
                return
            elif lists[mid][0] < timestamp:
                start = mid
            else:
                end = mid
                
        # if lists[end][0] == timestamp:
        #     lists[end] = (timestamp, value)            
        #     self.mapping[key] = lists
        #     return
        if lists[end][0] < timestamp:
            lists.insert(end + 1, (timestamp, value))
            self.mapping[key] = lists
            return
        # if lists[start][0] == timestamp:
        #     lists[start] = (timestamp, value)            
        #     self.mapping[key] = lists
        #     return
        if lists[start][0] < timestamp:
            lists.insert(start + 1, (timestamp, value))
            self.mapping[key] = lists
            return
        
        
   

    def get(self, key: str, timestamp: int) -> str:
        lists = self.mapping[key]
        if not lists:
            return ''
        start, end = 0, len(lists) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if lists[mid][0] == timestamp:
                return lists[mid][1]
            elif lists[mid][0] < timestamp:
                start = mid
            else:
                end = mid
                
        if lists[end][0] <= timestamp:
            return lists[end][1]
        if lists[start][0] <= timestamp:
            return lists[start][1]
        return ''
    




# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.store = {}
    
    def search_time(self,values, time, start, end):
        n = len(values)
        index = int((start + end) / 2)
        if (end - start) <= 3:
            cur = end
            while cur >= start:
                if values[cur][1] <= time:
                    return values[cur][0]
                cur -= 1
            return \"\"
                
        if values[index][1] == time:
            return values[index][0]
        elif values[index][1] < time:
            start = index
        else:
            end = index
        return self.search_time(values, time, start, end)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.store:
            self.store[key].append((value, timestamp))
        else:
            self.store[key] = [(value, timestamp)]

    def get(self, key: str, timestamp: int) -> str:
        if key in self.store:
            values = self.store[key]
            return self.search_time(values, timestamp, 0, len(values)-1)
        else:
            return \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.mapping = collections.defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        lists = self.mapping[key]
        if not lists:
            self.mapping[key] = [(timestamp, value)]
            return
        start, end = 0, len(lists) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if lists[mid][0] == timestamp:
                self.mapping[key][mid] = (timestamp, value)
                return
            elif lists[mid][0] < timestamp:
                start = mid
            else:
                end = mid
                
        # if lists[end][0] == timestamp:
        #     lists[end] = (timestamp, value)            
        #     self.mapping[key] = lists
        #     return
        if lists[end][0] < timestamp:
            lists.insert(end + 1, (timestamp, value))
            self.mapping[key] = lists
            return
        if lists[start][0] == timestamp:
            lists[start] = (timestamp, value)            
            self.mapping[key] = lists
            return
        if lists[start][0] < timestamp:
            lists.insert(start + 1, (timestamp, value))
            self.mapping[key] = lists
            return
        
        
   

    def get(self, key: str, timestamp: int) -> str:
        lists = self.mapping[key]
        if not lists:
            return ''
        start, end = 0, len(lists) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if lists[mid][0] == timestamp:
                return lists[mid][1]
            elif lists[mid][0] < timestamp:
                start = mid
            else:
                end = mid
                
        if lists[end][0] <= timestamp:
            return lists[end][1]
        if lists[start][0] <= timestamp:
            return lists[start][1]
        return ''
    




# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        \"\"\"
        self.data = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if not self.data[key]:
            return \"\"
        start = 0
        end = len(self.data[key]) - 1
        while start < end:
            mid = start + (end-start) // 2
            if self.data[key][mid][0] <= timestamp and self.data[key][mid+1][0] > timestamp:
                return self.data[key][mid][1]
            if self.data[key][mid][0] <= timestamp:
                start = mid + 1
            else:
                end = mid - 1
        
        return self.data[key][-1][1] if self.data[key][-1][0] <= timestamp else \"\"


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

class TimeMap:

    def __init__(self):
        \"\"\"
        Initialize your data structure here.
        
        10/02: my
        use dict; 
        
        need to bisect to get the timestamp.  binary search. 
        
        like find first version f
        
        value is an object of [value, list of timestamp. ]
        
        because timesteamp are strictly increasing, so it is monolitically increasing.
        
        1 3 5 7 9  f(4)=3
        
        # BUG Forget self.d self!!!
        
        # BUG max_idx=max(l, max_idx)  max_idx cannot be None, > is not supported between instance of none type and int.
        \"\"\"
        self.d = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.d:
            self.d[key].append((timestamp, value))
        else:
            self.d[key] = [(timestamp, value)]
        

    def get(self, key: str, timestamp: int) -> str:
        if key in self.d:
            return self.helper(timestamp, self.d[key])
        else:
            return ''
            
    def helper(self, target, arr):
        # target is the timestamp input
        l,r = 0, len(arr)-1
        max_idx=-1
        while l<=r:
            m = (l+r)//2
            if target==arr[m][0]:
                # there is only 1 timestamp matche due to strictly increasing.
                return arr[m][1]
            # this timestamp is too large, need to find left
            elif arr[m][0]>target:
                r=m-1
            # BUG: mid is a valid one! not left!
            # mid is a valid one! not left! but not sure whether it is the largest
            else:
                l=m+1
                
                max_idx=max(m, max_idx)
        return '' if max_idx==-1 else arr[max_idx][1]  


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)