class Location:
    def __init__(self, lat, long, timestamp):
        self.lat = lat
        self.long = long
        self.timestamp = timestamp

    def __str__(self):
        return f"({self.lat}{self.long}{self.timestamp})"

class LocationStore:
    def __init__(self):
        # Use a hashmap: user_id -> [Location]
        self.store = {}

    def get(self, user_id, query_time):
        if user_id not in self.store:
            return None

        # Get all the locations of user
        locations = self.store[user_id]
        n = len(locations)

        # Find the nearest timestamp
        left = 0
        right = n - 1

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

            # Current location
            loc = locations[mid]

            if loc.timestamp < query_time:
                left = mid + 1
            else:
                right = mid - 1

        return locations[left]

    def set(self, user_id, location):
        if user_id not in self.store:
            self.store[user_id] = []

        self.store[user_id].append(location)


def main():
    locationStore = LocationStore()

    # user_id = 1, (1, 3, 1), (2, 5, 3), (3, 5, 5)
    location_1 = Location(1,3,1)
    location_2 = Location(2,5,3)
    location_3 = Location(3,5,5)

    # Set location store
    locationStore.set(1, location_1)
    locationStore.set(1, location_2)
    locationStore.set(1, location_3)

    # Get location
    result = locationStore.get(1, 5)
    print(result)


main()

class FuzzyClass:
    ALPHABET_SIZE = 26
    BASE_CHR = ord('a')

    def __init__(self, secret):
        self.secret = secret
        self.block_size = len(secret)

    def _idx2char(self, idx):
        # 1: 'a', 2: 'b', 3: 'c'
        return (idx - 1 + BASE_CHR)

    def _char2idx(self, chr):
        # 'a': 1, 'b': 2,...
        return ord(chr) - BASE_CHR

    def _addChar(self, chr1, chr2):
        v1 = self._char2idx(chr1)
        v2 = self._char2idx(chr2)

        # total
        total = (v1 + v2) % ALPHABET_SIZE
        return self._idx2char(total)

    def _subChar(self, chr1, chr2):
        v1 = self._char2idx(chr1)
        v2 = self._char2idx(chr2)

        # total
        sub = (v1 - v2) % ALPHABET_SIZE

        # Have handle case v1 - v2 negative
        return self._idx2char(sub)

    def _addString(self, str1, str2):
        result = []

        for c1, c2 in zip(str1, str2):
            addChar = self._addChar(c1, c2)
            result.append(addChar)

        return ''.join(result)

    def encrypt(self, data):
        result = []

        for i, chr in enumerate(data):
            secret_chr = self.secret[i % ALPHABET_SIZE]
            result.append(self._addChar(chr, secret_chr))

        return "".join(result)


    def descrypt(self, data):
        result = []

        for i, chr in enumerate(data):
            secret_chr = self.secret[i % ALPHABET_SIZE]
            result.append(self._subChar(chr, secret_chr))

        return "".join(result)


    def hash(self, data):
        # Hash the secret based on data
        N = len(data)

        # Add temp value
        temp = self.secret

        for i in range(0, N, self.block_size):
            block_str = self.secret[i, i + block_size]
            temp = self._addString(temp, block_str)

        return temp

import random
from collections import defaultdict

class InsertDeleteRandomO(1):
    def __init__(self):
        self.arr = []

        # Use for quick query
        self.pos = defaultdict(set) # id: hashset of indexes, 4: {1,2,3}

    def insert(self, id: int) -> bool:
        existed = id in self.pos and len(self.pos[id]) > 0

        # Add to arr and pos
        self.arr.append(id)
        self.pos[id].add(len(self.arr) - 1)

        return existed


    def delete(self, id: int) -> bool:
        if id not in self.pos or len(self.pos[id]) == 0:
            return False

        # Get remove_idx and assign it with last_val, pop last_val
        remove_idx = self.pos[id].pop()
        last_val = self.arr[-1]

        # Add to arr
        self.arr[remove_idx] = last_val
        self.dict[last_val].add(remove_idx)

        # Remove last_val
        self.dict[last_val].discard(len(self.arr) - 1)
        self.arr.pop()

        return True

    def random(self) -> int:
        return random.choice(self.arr)

from collections import deque
from typing import List

class PoliceGarage:
    def __init__(self, carIds: List[str]):
        # Stack of availables car
        self.stack = deque(carIds)

        # Queue of check-out cars
        self.check_out = deque()

    # Move to stack to checkout
    def checkoutCar(self) -> str:
        if not self.stack:
            raise Exception("No car can checkout")

        car = self.stack.pop()
        self.checkout.append(car)

        return car

    # Move from checkout to stack
    def checkInCar(self) -> str:
        if not self.checkout:
            raise Exception("No car to check-in")

        car = self.check_out.popLeft()
        self.stack.append(car)

        return car

    def getNextCars(self, n: int) -> List[str]:
        temp_stack = deque(self.stack)
        temp_queue = deque(self.queue)

        # All the queue checkin
        while temp_queue:
            temp_stack.append(temp_queue.popLeft())

        # Filter n car in stack
        result = []
        for i in range(min(n, len(temp_stack))):
            result.append(temp_stack.pop())

        return result

class InOrderSuffle:
    # Naive Solution
    def isInterLeave(self, s1: str, s2: str, s3: str) -> bool:
        n = len(s1)
        m = len(s2)
        k = len(s3)

        if k != n + m:
            return False

        def dfs(i, j):
            # Base case
            if i == n and j == m:
                return True

            k = i + j

            # Backtrack
            if i < len(s1) and s1[i] == s3[k]:
                if dfs(i + 1, j):
                    return True

            if j < len(s2) and s2[j] == s3[k]:
                if dfs(i, j + 1):
                    return True

            return False

        return dfs(0, 0)

    # Top-down solution
    def isInterLeave(self, s1: str, s2: str, s3: str) -> bool:
        n = len(s1)
        m = len(s2)
        k = len(s3)

        if k != n + m:
            return False

        dp = {}

        def dfs(i, j):
            # Step 1: Base case
            if i == n and j == m:
                return True

            k = i + j

            if (i, j) in dp:
                return dp[(i, j)]

            # Step 2: Backtrack
            res = False

            if i < len(s1) and s1[i] == s3[k]:
                res = dfs(i + 1, j)

            if j < len(s2) and s2[j] == s3[k]:
                res = dfs(i, j + 1)

            dp[(i, j)] = res

            return res

        return dfs(0, 0)


    # Bottom-up solution
    def isInterLeave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, k = len(s1), len(s2), len(s3)

        if m + n != k:
            return False

        # Step 1: Base case
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] and s2[j - 1] = s3[j - 1]

        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] = s3[i - 1]

        # Step 2: Update
        for i in range(m + 1):
            for j in range(n + 1):
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1])
                        or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])

        return dp[m][n]

import heapq

class Solution:
    def _distance(self, x, y):
        return x ** 2 + y ** 2

    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        maxHeap = []

        for x, y in points:
            # heap push
            dist = -self._distance(x, y)
            heapq.heappush(maxHeap, [dist, x, y])

            if len(maxHeap) > k:
                heapq.heappop(maxHeap)

        res = []
        while maxHeap:
            dist, x, y = heapq.heappop(maxHeap)
            res.append([x, y])

        return res

class Solution:

    # DFS
    def numIslands(self, grid: List[List[str]]) -> int:
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        ROWS, COLS = len(grid), len(grid[0])

        def dfs(r, c):
            # Base case
            if r < 0 or r >= ROWS or c < 0 or c >= COLS or grid[r][c] == "0":
                return

            # Backtrack or add visited
            grid[r][c] = "0"
            for dr, dc in directions:
                dfs(r + dr, c + dc)

        count = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1":
                    dfs(r, c)
                    count += 1

        return count

from collections import deque

class Solution:

    # DFS
    def numIslands(self, grid: List[List[str]]) -> int:
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        ROWS, COLS = len(grid), len(grid[0])

        def bfs(r, c):
            q = deque()
            grid[r][c] = "0"
            q.append([r, c])

            while q:
                row, col = q.popleft()

                for dr, dc in directions:
                    nr, nc = row + dr, col + dc

                    # Base case
                    if nr < 0 or nr >= ROWS or nc < 0 or nc >= COLS or grid[nr][nc] == "0":
                        continue

                    # Backtrack
                    q.append([nr, nc])
                    grid[nr][nc] = "0"

        count = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1":
                    bfs(r, c)
                    count += 1

        return count

class Solution:
    def alphaNum(self, c):
        return (ord('A') <= ord(c) <= ord('Z') or
                ord('a') <= ord(c) <= ord('z') or
                ord('0') <= ord(c) <= ord('9'))

    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left <= right:
            while left < right and not self.alphaNum(s[left]):
                left += 1

            while left < right and not self.alphaNum(s[right]):
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set()
        negDiag = set()

        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            # Base case
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return

            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue

                # Current
                col.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                board[r][c] = "Q"

                # Backtrack another row
                backtrack(r + 1)

                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)
                board[r][c] = "."

        backtrack(0)
        return res

class Solution:
    def romanToInt(self, s: str) -> int:
        roman = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }

        n = len(s)
        res = 0
        for i in range(n):
            if i + 1 < len(s) and roman[s[i]] < roman[s[i + 1]]:
                res -= roman[s[i]]
            else:
                res += roman[s[i]]

        return res

class Solution:
    def intToRoman(self, num: int) -> str:
        roman = {
            "M": 1000,
            "CM": 900,
            "D": 500,
            "CD": 400,
            "C": 100,
            "XC": 90,
            "L": 50,
            "XL": 40,
            "X": 10,
            "IX": 9,
            "V": 5,
            "IV": 4,
            "I": 1
        }

        res = ""
        for key, value in roman.items():
            count = num // value

            if count:
                res += count * key
                num -= count * value

        return res

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        def dfs(i, j):

            # Base case
            if i == m:
                return n - j

            if j == n:
                return m - i

            if word1[i] == word2[j]:
                return dfs(i + 1, j + 1)
            else:
                # Backtrack
                res = min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1))
                return res + 1

        return dfs(0, 0)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = {}

        def dfs(i, j):
            # Base case
            if i == m:
                return n - j

            if j == n:
                return m - i

            if (i, j) in dp:
                return dp[(i, j)]

            if word1[i] == word2[j]:
                dp[(i, j)] = dfs(i + 1, j + 1)
            else:
                # Backtrack
                res = min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1))
                dp[(i, j)] = res + 1

            return dp[(i, j)]

        return dfs(0, 0)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # Base case
        n, m = len(word1), len(word2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            # Convert word[:i] to empty string
            dp[i][0] = i
        for j in range(m + 1):
            # Convert empty string to word[:j]
            dp[0][j] = j

        # Update
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

        return dp[n][m]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1

            charSet.add(s[r])
            res = max(res, r - l + 1)

        return res