def twoSum(nums, target):    d = {}    for i, n in enumerate(nums):        if target - n in d:            return [d[target-n], i]        d[n] = i

import heapqdef findKthLargest(nums, k):    return heapq.nlargest(k, nums)[-1]

def maxArea(height):    l, r = 0, len(height)-1    res = 0    while l < r:        res = max(res, min(height[l], height[r]) * (r-l))        if height[l] < height[r]: l += 1        else: r -= 1    return res

def moveZeroes(nums):    idx = 0    for n in nums:        if n != 0:            nums[idx] = n            idx += 1    nums[idx:] = [0] * (len(nums)-idx)

def sortColors(nums): l, mid, r = 0, 0, len(nums)-1    while mid <= r:        if nums[mid] == 0:            nums[l], nums[mid] = nums[mid], nums[l]            l += 1; mid += 1        elif nums[mid] == 2:            nums[mid], nums[r] = nums[r], nums[mid]            r -= 1        else:            mid += 1

def singleNumber(nums):    res = 0    for n in nums:        res ^= n    return res

def majorityElement(nums):    cnt, res = 0, 0    for n in nums:        if cnt == 0:            res = n        cnt += 1 if n == res else -1    return res

def merge(intervals):    intervals.sort()    res = [intervals[0]]    for s, e in intervals[1:]:        if s <= res[-1][1]:            res[-1][1] = max(res[-1][1], e)        else:            res.append([s, e])    return res

def reverseList(head):    pre, cur = None, head    while cur:        nxt = cur.next        cur.next = pre        pre, cur = cur, nxt    return pre

def reverseList(head):    if not head or not head.next:        return head    new_head = reverseList(head.next)    head.next.next = head    head.next = None    return new_head

def reverseBetween(head, left, right):    dummy = ListNode(next=head)    pre = dummy    for _ in range(left-1):        pre = pre.next    cur = pre.next    for _ in range(right-left):        nxt = cur.next        cur.next = nxt.next        nxt.next = pre.next        pre.next = nxt    return dummy.next

def hasCycle(head):    slow = fast = head    while fast and fast.next:        slow = slow.next        fast = fast.next.next        if slow == fast:            return True    return False

def detectCycle(head):    slow = fast = head    while fast and fast.next:        slow = slow.next        fast = fast.next.next        if slow == fast:            p = head            while p != slow:                p = p.next                slow = slow.next            return p    return None

def mergeTwoLists(l1, l2):    dummy = cur = ListNode()    while l1 and l2:        if l1.val < l2.val:            cur.next = l1            l1 = l1.next        else:            cur.next = l2            l2 = l2.next        cur = cur.next    cur.next = l1 or l2    return dummy.next

def mergeTwoLists(l1, l2):    if not l1: return l2    if not l2: return l1    if l1.val < l2.val:        l1.next = mergeTwoLists(l1.next, l2)        return l1    else:        l2.next = mergeTwoLists(l1, l2.next)        return l2

def swapPairs(head):    dummy = ListNode(next=head)    pre = dummy    while pre.next and pre.next.next:        a = pre.next        b = a.next        pre.next, b.next, a.next = b, a, b.next        pre = a    return dummy.next

def swapPairs(head):    if not head or not head.next:        return head    new_head = head.next    head.next = swapPairs(new_head.next)    new_head.next = head    return new_head

def removeNthFromEnd(head, n):    dummy = ListNode(next=head)    fast = slow = dummy    for _ in range(n+1):        fast = fast.next    while fast:        slow = slow.next        fast = fast.next    slow.next = slow.next.next    return dummy.next

def isPalindrome(head):    slow = fast = head    pre = None    while fast and fast.next:        fast = fast.next.next        nxt = slow.next        slow.next = pre        pre = slow        slow = nxt    if fast:        slow = slow.next    while pre and pre.val == slow.val:        pre = pre.next        slow = slow.next    return not pre

def lengthOfLongestSubstring(s):    d = {}    left = res = 0    for right, c in enumerate(s):        if c in d and d[c] >= left:            left = d[c] + 1        d[c] = right        res = max(res, right-left+1)    return res

def longestPalindrome(s):    def expand(l, r):        while l >= 0 and r < len(s) and s[l] == s[r]:            l -= 1            r += 1        return s[l+1:r]    res = ''    for i in range(len(s)):        res = max(res, expand(i,i), expand(i,i+1), key=len)    return res

def isValid(s):    stack = []    d = {')':'(', ']':'[', '}':'{'}    for c in s:        if c not in d:            stack.append(c)        else:            if not stack or stack.pop() != d[c]:                return False    return not stack

def addStrings(num1, num2):    i, j, carry = len(num1)-1, len(num2)-1, 0    res = []    while i >= 0 or j >= 0 or carry:        a = int(num1[i]) if i >= 0 else 0        b = int(num2[j]) if j >= 0 else 0        carry, t = divmod(a + b + carry, 10)        res.append(str(t))        i -= 1; j -= 1    return ''.join(res[::-1])

def multiply(num1, num2):    if num1 == "0" or num2 == "0": return "0"    m, n = len(num1), len(num2)    res = [0] * (m + n)    for i in range(m-1, -1, -1):        a = int(num1[i])        for j in range(n-1, -1, -1):            b = int(num2[j])            res[i+j+1] += a * b            res[i+j] += res[i+j+1] // 10            res[i+j+1] %= 10    idx = 0    while res[idx] == 0: idx += 1    return ''.join(map(str, res[idx:]))

def reverseWords(s):    return ' '.join(s.split()[::-1])

def minWindow(s, t):    from collections import Counter    need = Counter(t)    window = {}    left = valid = 0    start, min_len = 0, float('inf')    for right, c in enumerate(s):        if c in need:            window[c] = window.get(c, 0) + 1            if window[c] == need[c]:                valid += 1        while valid == len(need):            if right - left + 1 < min_len:                start, min_len = left, right - left + 1            d = s[left]            if d in need:                if window[d] == need[d]:                    valid -= 1                window[d] -= 1            left += 1    return s[start:start+min_len] if min_len != float('inf') else ''

def longestCommonPrefix(strs):    if not strs: return ''    pre = strs[0]    for s in strs[1:]:        while not s.startswith(pre):            pre = pre[:-1]            if not pre: return ''    return pre

def levelOrder(root):    if not root: return []    q = deque([root])    res = []    while q:        level = []        for _ in range(len(q)):            node = q.popleft()            level.append(node.val)            if node.left: q.append(node.left)            if node.right: q.append(node.right)        res.append(level)    return res

def maxDepth(root):    if not root: return 0    return max(maxDepth(root.left), maxDepth(root.right)) + 1

def diameterOfBinaryTree(root):    res = 0    def dfs(node):        nonlocal res        if not node: return 0        l = dfs(node.left)        r = dfs(node.right)        res = max(res, l + r)        return max(l, r) + 1    dfs(root)    return res

def invertTree(root):    if not root: return None    root.left, root.right = invertTree(root.right), invertTree(root.left)    return root

def isSymmetric(root):    def dfs(l, r):        if not l and not r: return True        if not l or not r: return False        return l.val == r.val and dfs(l.left, r.right) and dfs(l.right, r.left)    return dfs(root, root)

def hasPathSum(root, targetSum):    if not root: return False    if not root.left and not root.right:        return root.val == targetSum    return hasPathSum(root.left, targetSum-root.val) or hasPathSum(root.right, targetSum-root.val)

def lowestCommonAncestor(root, p, q):    if root.val > p.val and root.val > q.val:        return lowestCommonAncestor(root.left, p, q)    if root.val < p.val and root.val < q.val:        return lowestCommonAncestor(root.right, p, q)    return root

def isValidBST(root):    def dfs(node, l, r):        if not node: return True        if not (l < node.val < r): return False        return dfs(node.left, l, node.val) and dfs(node.right, node.val, r)    return dfs(root, float('-inf'), float('inf'))

def climbStairs(n):    a, b = 1, 1    for _ in range(n-1):        a, b = b, a+b    return b

def maxSubArray(nums):    res = cur = nums[0]    for n in nums[1:]:        cur = max(n, cur+n)        res = max(res, cur)    return res

def rob(nums):    a, b = 0, 0    for n in nums:        a, b = b, max(b, a+n)    return b

def rob(nums):    def helper(l, r):        a = b = 0        for i in range(l, r):            a, b = b, max(b, a+nums[i])        return b    n = len(nums)    if n == 1: return nums[0]    return max(helper(0, n-1), helper(1, n))

def coinChange(coins, amount):    dp = [float('inf')] * (amount+1)    dp[0] = 0    for c in coins:        for i in range(c, amount+1):            dp[i] = min(dp[i], dp[i-c] + 1)    return dp[amount] if dp[amount] != float('inf') else -1

def lengthOfLIS(nums):    tails = []    for n in nums:        if not tails or n > tails[-1]:            tails.append(n)        else:            import bisect            tails[bisect.bisect_left(tails, n)] = n    return len(tails)

def longestCommonSubsequence(text1, text2):    m, n = len(text1), len(text2)    dp = [[0]*(n+1) for _ in range(m+1)]    for i in range(1, m+1):        for j in range(1, n+1):            if text1[i-1] == text2[j-1]:                dp[i][j] = dp[i-1][j-1] + 1            else:                dp[i][j] = max(dp[i-1][j], dp[i][j-1])    return dp[m][n]

def minPathSum(grid):    m, n = len(grid), len(grid[0])    for i in range(m):        for j in range(n):            if i == 0 and j == 0: continue            elif i == 0: grid[i][j] += grid[i][j-1]            elif j == 0: grid[i][j] += grid[i-1][j]            else: grid[i][j] += min(grid[i-1][j], grid[i][j-1])    return grid[-1][-1]

def dailyTemperatures(T):    res, stack = [0]*len(T), []    for i, t in enumerate(T):        while stack and T[stack[-1]] < t:            idx = stack.pop()            res[idx] = i - idx        stack.append(i)    return res

def largestRectangleArea(heights):    stack, heights = [-1], heights + [0]    res = 0    for i, h in enumerate(heights):        while heights[stack[-1]] > h:            height = heights[stack.pop()]            width = i - stack[-1] - 1            res = max(res, height * width)        stack.append(i)    return res

def permute(nums):    res = []    def back(path, rest):        if not rest:            res.append(path)            return        for i in range(len(rest)):            back(path+[rest[i]], rest[:i]+rest[i+1:])    back([], nums)    return res

def subsets(nums):    res = []    def dfs(path, start):        res.append(path)        for i in range(start, len(nums)):            dfs(path+[nums[i]], i+1)    dfs([], 0)    return res

def combinationSum(candidates, target):    res = []    def dfs(path, start, remain):        if remain == 0:            res.append(path)            return        for i in range(start, len(candidates)):            if candidates[i] > remain: continue            dfs(path+[candidates[i]], i, remain-candidates[i])    dfs([], 0, target)    return res

def exist(board, word):    m, n = len(board), len(board[0])    dirs = [(-1,0),(1,0),(0,-1),(0,1)]    def dfs(i, j, k):        if not (0<=i<m and 0<=j<n) or board[i][j] != word[k]:            return False        if k == len(word)-1:            return True        tmp, board[i][j] = board[i][j], '#'        for dx, dy in dirs:            if dfs(i+dx, j+dy, k+1):                return True        board[i][j] = tmp        return False    for i in range(m):        for j in range(n):            if dfs(i, j, 0):                return True    return False

class MedianFinder:    def __init__(self):        import heapq        self.small = []        self.large = []    def addNum(self, num):        heapq.heappush(self.small, -num)        heapq.heappush(self.large, -heapq.heappop(self.small))        if len(self.large) > len(self.small) + 1:            heapq.heappush(self.small, -heapq.heappop(self.large))    def findMedian(self):        if len(self.large) > len(self.small):            return self.large[0]        return (self.large[0] - self.small[0]) / 2

def topKFrequent(nums, k):    from collections import Counter    import heapq    cnt = Counter(nums)    return heapq.nlargest(k, cnt.keys(), key=cnt.get)

from collections import OrderedDictclass LRUCache:    def __init__(self, capacity):        self.cap = capacity        self.d = OrderedDict()    def get(self, key):        if key not in self.d: return -1        self.d.move_to_end(key)        return self.d[key]    def put(self, key, value):        if key in self.d:            self.d.move_to_end(key)        self.d[key] = value        if len(self.d) > self.cap:            self.d.popitem(last=False)

def search(nums, target):    l, r = 0, len(nums)-1    while l <= r:        mid = (l+r)//2        if nums[mid] == target:            return mid        if nums[l] <= nums[mid]:            if nums[l] <= target < nums[mid]:                r = mid - 1            else:                l = mid + 1        else:            if nums[mid] < target <= nums[r]:                l = mid + 1            else:                r = mid - 1    return -1