class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        if len(nums) == 0: return False
        for x in nums:
            if x > len(nums) - 1 or x < 0:
                return None
        
        rec = dict()
        
        for a in nums:
            if a not in rec:
                rec[a] = 1
            else:
                return a
        return None

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        if len(nums) == 0: return False
        for x in nums:
            if x > len(nums) - 1 or x < 0:
                return None
        
        for i in range(len(nums)):
            while nums[i] != i:
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return None

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        if len(nums) == 0: return False
        n = len(nums) - 1 #  1<= a <= n while len(nums) == n+1

        for x in nums:
            if x > n or x < 1:  
                return None
        
        # binary search
        # start, high
        start = 1 # start from 1 !!!
        end = n
        
        while start <= end:
            # split into two half
            mid = (end - start) // 2 + start
            # count how many elements in this interval 
            count = sum([1 for x in nums if start <= x <= mid])
            
            # if the interval is one-element length, then 
            # check if count > 1
            if start == end:
                if count > 1: return start
                else:
                    break
            
            if count > (mid - start + 1): # in this interval
                end = mid
            else:
                start = mid + 1 # in the left interval
            
        return None

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]: return 0
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        # dp 表示以 matrix[i-1][j-1]为右下角的最大正方形的边长
        # matrix[i-1][j-1] 为 1 时，它的边长向上延伸，向左延伸
        # 显然是由 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 
        # 对应的三个正方形的最短边长决定的（画图更容易理解）
        # dp[i][j] = matrix[i-1][j-1] == 1 && min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

        max_edge = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if matrix[i-1][j-1] == '1':
                    dp[i][j] = min(
                        dp[i-1][j],
                        dp[i][j-1], 
                        dp[i-1][j-1]
                    ) + 1
                    if dp[i][j] > max_edge: 
                        max_edge = dp[i][j]
        return max_edge ** 2

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0

        l, r = 0, len(height) - 1

        total = 0
        barsum = 0
        level = 1
        maxlevel = max(height)
        while l <= r:
            # 当 l==r 时，都指向最高的柱子，
            # 没必要再 level++ 了
            # 此时 total 已经在上一轮统计完毕了
            # 只需要再统计一下 barsum
            if l == r:
                barsum += level - 1
                break
            while l <= r and height[l] < level: 
                barsum += height[l]
                l += 1
            while l <= r and height[r] < level:
                barsum += height[r]
                r -= 1
            total += r - l + 1
            level += 1
        # print(total, barsum)

        return total - barsum
           

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0

        n = len(height)

        leftmax = [0] * n
        for i in range(1, n): leftmax[i] = max(leftmax[i-1], height[i-1])
        
        rightmax = [0] * n
        for i in range(n-2, -1, -1): rightmax[i] = max(rightmax[i+1], height[i+1])
        
        total = 0
        for i in range(n):
            sidemin = min(leftmax[i], rightmax[i])
            if sidemin - height[i] > 0:
                total += sidemin - height[i]
        return total

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def check(a, b):
            if not b:
                return True
            if not a or a.val != b.val:
                return False
            return check(a.left, b.left) and check(a.right, b.right)

        return bool(A and B) \
            and (check(A, B) \
            or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def check(a, b):
            if not b:
                return True
            if not a or a.val != b.val:
                return False
            return check(a.left, b.left) and check(a.right, b.right)

        if not A or not B: return False
        if check(A, B): return True
        return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        """ 相当于 10 叉前缀树的遍历，找第 k 个节点 """
        cur = 1
        k = k - 1 # 扣除当前节点 1

        while k:
            count = self.get_count(cur, n)

            # 如果 k 不在cur 为前缀的子树里
            # 下一步考察 cur+1 为前缀的子树
            if count <= k:
                k -= count
                cur += 1
            # 如果 k 在 cur 为前缀的子树里
            # 下一步往 cur 的子树继续考察
            # 第一个先考察 10*cur 为前缀的子树
            else:
                k -= 1
                cur *= 10

        return cur

    def get_count(self, prefix, n):
        """ 统计以 prefix 为前缀的这一层有多少节点 """
        # nxt 可以看做以 cur 前缀的 10 叉树的层的上界
        cur, nxt = prefix, prefix + 1
        cnt = 0
        while cur <= n:
            # 如果 n+1 不如 nxt 大，说明这一层不是满 10 叉树
            # 这一层的节点数为 n - cur + 1
            cnt += min(n+1, nxt) - cur
            cur *= 10
            nxt *= 10
        return cnt 

class Solution:
    def translateNum(self, num: int) -> int:
        # dp[i] = dp[i-1] + dp[i-2] if (i-1,i) valid else dp[i+1]

        nums = str(num)
        n = len(nums)
        dp = [0] * (n+1)
        dp[0] = dp[1] = 1

        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2] if 10 <= int(nums[i-2:i]) < 26 \
                else dp[i-1]

        return dp[n]

class Solution:
    def translateNum(self, num: int) -> int:
        # dp[i] = dp[i-1] + dp[i-2] if (i-1,i) valid else dp[i-1]
        #    b = b + a | a = b
        #    b = b | a = b
        nums = str(num)
        n = len(nums)

        a, b = 1, 1
        for i in range(2, n+1):
            b, a = (a+b, b) if "10" <= nums[i-2:i] < "26" \
                else (b, b)

        return b

class Solution:
    def translateNum(self, num: int) -> int:
        # dp[i] = dp[i-1] + dp[i-2] if (i-1,i) valid else dp[i-1]
        #    b = b + a | a = b
        #    b = b | a = b
        #    x, y : i-1, i
        a, b = 1, 1
        
        x = num % 10 # i-1

        while num:
            num //= 10
            y = num % 10 # i
            b, a = (b+a, b) if 10 <= 10*y+x < 26 \
                else (b, b)
            x = y
        return b

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        visited = [[False] * cols for _ in range(rows)]
        delta = ((0, 1), (1, 0), (0, -1), (-1, 0))

        def _dfs(i, j, visited, cur_idx):
            # check boundary
            if 0 <= i < rows and 0 <= j < cols \
                and not visited[i][j] and board[i][j] == word[cur_idx]:

                visited[i][j] = True
                if cur_idx == len(word) - 1: return True

                exist_path = any(
                    _dfs(i+di, j+dj, visited, cur_idx+1)
                    for di, dj in delta
                )
                if not exist_path:
                    visited[i][j] = False
                return exist_path
            return False

        for i in range(rows):
            for j in range(cols):
                if _dfs(i, j, visited, 0):
                    return True
        return False

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        delta = ((0, 1), (1, 0), (0, -1), (-1, 0))

        def _dfs(i, j, cur_idx):
            # check boundary
            if board[i][j] == word[cur_idx]:
                if cur_idx == len(word) - 1: return True

                tmp, board[i][j] = board[i][j], " "
                exist_path = any(
                    _dfs(i+di, j+dj, cur_idx+1)
                    for di, dj in delta 
                    if 0 <= i+di < rows and 0 <= j+dj < cols
                )
                board[i][j] = tmp
                return exist_path
            return False

        for i in range(rows):
            for j in range(cols):
                if _dfs(i, j, 0):
                    return True
        return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, cur = None, head
        
        while cur is not None:
            # save next node
            nxt = cur.next

            cur.next = prev
            prev = cur
            cur = nxt

        return prev

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        
        rev_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return rev_head

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        low, high = 0, len(numbers) -1
        mid = low
        while numbers[low] >= numbers[high]:
            if high - low == 1:
                mid = high
                break
            
            mid = (low + high) >> 1

            # 如果 low，high，mid 相同，即无法判断 mid 在哪个数组
            # 需要顺序查找最小数字
            if numbers[low] == numbers[mid] == numbers[high]:
                tmp = numbers[low]
                for i in range(low+1, high+1):
                    if numbers[i] < tmp: tmp = numbers[i]
                return tmp

            if numbers[mid] >= numbers[low]:
                low = mid
            elif numbers[mid] <= numbers[high]:
                high = mid

        return numbers[mid]

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        low, high = 0, len(numbers) -1

        while low < high:
            mid = (high + low) >> 1
            
            if numbers[mid] > numbers[high]:
                low = mid + 1
            elif numbers[mid] < numbers[high]:
                high = mid
            else:
                high -= 1

        return numbers[low] # low == high

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        dp = [0] * len(s)
        maxlen = 0

        for i in range(len(s)):
            if s[i] == ')':
                if i > 0 and s[i-1] == '(': 
                    dp[i] = (dp[i-2] if i > 1 else 0) + 2
                elif (lp := i - dp[i-1] - 1) >= 0 and s[lp] == '(' and s[i-1] == ')':
                    dp[i] = dp[i-1] + (dp[lp-1] if lp > 0 else 0) + 2
                maxlen = max(maxlen, dp[i])
        return maxlen

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def check_sym(t1, t2):
            # 判断 t1, t2 两棵树是否对称

            # 同时越过叶节点
            if not t1 and not t2: return True
            # 一个越过了叶节点一个没有
            # 或者都没越过叶节点，但是该根节点值不相同
            if not t1 or not t2 or t1.val != t2.val: return False
            return check_sym(t1.left, t2.right) and check_sym(t1.right, t2.left)
        
        # 对称二叉树自己和自己对称
        return check_sym(root, root) if root else False
        # 直接判断左右子树会更快
        # return check_sym(root.left, root.right) if root else False

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True

        q = []
        q.append(root.left)
        q.append(root.right)
        
        while q:
            elem1, elem2 = q.pop(0), q.pop(0)
            if not elem1 and not elem2:
                continue
            if not elem1 or not elem2 or elem1.val != elem2.val:
                return False
            
            q.extend([elem1.left, elem2.right, elem1.right, elem2.left])
        
        return True

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not arr or k <= 0 or k > len(arr): return []

        start, end = 0, len(arr) -1
        index = self.partition(arr, start, end)

        while index != k-1:
            if index > k-1:
                end = index - 1
                index = self.partition(arr, start, index-1)
            if index < k-1:
                start = index + 1
                index = self.partition(arr,start, end)

        # print(arr)
        return arr[:k]

    def partition(self, arr, start, end):
        low = start
        high = end
        temp = arr[start]
        while low < high:
            while low < high and arr[high] >= temp:
                high -= 1
            # arr[low], arr[high] = arr[high], arr[low]
            while low < high and arr[low] <= temp:
                low += 1
            arr[low], arr[high] = arr[high], arr[low]
        arr[low], arr[start] = arr[start], arr[low]
        return low

    def partition2(self, array, l, r):
        x = array[r]
        i = l - 1
        for j in range(l, r):
            # find the one smaller than right
            if array[j] <= x:
                # small position
                i += 1
                array[i], array[j] = array[j], array[i]
        # i-th is the biggest small one, i+1 th is a big one
        # put right on this position cause right is the i+i th
        array[i+1], array[r] = array[r], array[i+1]
        return i + 1

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        def dfs(head):
            if not head:
                return None
            if head in visited:
                return visited[head] # copy of head
            
            copy = Node(head.val, None, None)
            visited[head] = copy
            copy.random = dfs(head.random)
            copy.next = dfs(head.next)

            return copy

        visited = {}
        return dfs(head)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        def bfs(head):
            if not head: return None
            q = collections.deque()
            q.append(head)
            clone = Node(head.val, None, None)
            visited[head] = clone
            while q:
                node = q.popleft()
                if node.next and node.next not in visited: 
                    q.append(node.next)
                    visited[node.next] = Node(node.next.val, None, None)
                visited[node].next = visited.get(node.next)
                if node.random and node.random not in visited: 
                    q.append(node.random)
                    visited[node.random] = Node(node.random.val, None, None)
                visited[node].random = visited.get(node.random)
            return visited[head]

        visited = {}
        return bfs(head)

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return 0

        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]

        dp[0][0] = grid[0][0]

        for i in range(m):
            for j in range(n):
                left = dp[i-1][j] if i - 1 >= 0 else 0
                top = dp[i][j-1] if j - 1 >= 0 else 0
                dp[i][j] = max(left, top) + grid[i][j]
        return dp[m-1][n-1]

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return 0

        m, n = len(grid), len(grid[0])
        dp = [0] * n

        for i in range(m):
            for j in range(n):
                left = dp[j-1] if j > 0 else 0
                dp[j] = max(left, dp[j]) + grid[i][j]

        return dp[n-1]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # deque 内只包含窗口内的值，维护的是有可能成为当前或未来窗口最大值的元素
        # deque 是一个单调递减队列，头元素是该窗口内最大的值
        # 每次移动窗口，如果队列中最大元素是左移出窗口的元素，删除掉他
        # 将新移入窗口的元素放入队列合适位置，小于它的元素都删除掉，
        # 因为有了这个比他们大的新元素，它们不可能成为未来任何窗口（k-1个）的最大值
        # 这样一来，队列中从左到右递增，并且数字排列顺序也和 nums 中一样（中间太小的已经被移出）
        # 所以窗口中最大值如果是左边界，它也只可能出现在队列的最左边
        if not nums: return []

        deque = collections.deque()

        # 未形成窗口 0~k-1
        for i in range(k):
            while deque and deque[-1] < nums[i]: deque.pop()
            deque.append(nums[i])

        res = [deque[0]]

        for r in range(k, len(nums)):
            # 队列中弹出移出窗口了的元素
            l = r - k + 1
            if deque[0] == nums[l-1]: deque.popleft()
            while deque and deque[-1] < nums[r]: deque.pop()
            deque.append(nums[r])
            res.append(deque[0])

        return res

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1

        # recursive
        if l1.val > l2.val:
            l1, l2 = l2, l1

        l1.next = self.mergeTwoLists(l1.next, l2)

        return l1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dumy = cur = ListNode(0)

        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 dumy.next

for j in range(1, n):
    for i in range(0, j)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)

        dp = [[False] * size for _ in range(size)]

        # dp[i][j] == (s[i] == s[j]) and (dp[i+1][j-1])
        maxlen = 1
        start = 0
        for j in range(1, size):
            for i in range(j):
                if s[i] == s[j]:
                    if (j-1) - (i+1) + 1 < 2:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = False
                
                if dp[i][j]:
                    curlen = j - i + 1
                    if curlen > maxlen:
                        maxlen = curlen
                        start = i

        return s[start:start+maxlen]

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        n, m = len(matrix), len(matrix[0])

        row, col = 0, m-1
        while row < n and col >= 0:  # row is increasing
            elem = matrix[row][col]
            if elem == target:
                return True
            elif target > elem:
                row += 1    # delete this row
            else:
                col -= 1    # delete this column
        return False

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

        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

        # base cases
        # word1 长度为 0 时，变成 word2的某个前缀 word2[:j] 需要 j 次插入
        for j in range(1, len2+1): dp[0][j] = j
        # 同理，word2 长度为 0 时，
        # word1的某个前缀 word1[:i] 变成变成 word2("") 需要 i 次删除
        for i in range(1, len1+1): dp[i][0] = i

        for i in range(1, len1+1):
            for j in range(1, len2+1):
                # 对应的两个字符相等，什么编辑都不需要做
                # 编辑距离等于 word1[:i-1] 与 word2[:j-1] 的编辑距离
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(
                        # 可以通过在 word1[:i] 后插入 w2[j] 变成 word2[:j], 
                        # 那首先至少需要先通过将 word[:i] 编辑成 word2[:j-1]
                        # 因此，编辑距离等于 word1[:i] 与 word2[:j-1]的编辑距离 + 1
                        dp[i][j-1] + 1, 
                        # 可以通过在 word1[:i] 后删除 w1[i] 变成 word2[:j], 
                        # 那首先至少需要先通过将 word[:i-1] 编辑成 word2[:j]
                        # 因此，编辑距离等于 word1[:i-1] 与 word2[:j]的编辑距离 + 1
                        dp[i-1][j] + 1,     
                        # 可以通过把 word1[:i] 的 w1[i] 替换成 w2[j] 使其变成 word2[:j], 
                        # 那首先至少需要先通过将 word[:i-1] 编辑成 word2[:j-1]
                        # 因此，编辑距离等于 word1[:i-1] 与 word2[:j-1]的编辑距离 + 1
                        dp[i-1][j-1] + 1,                            
                    )

        return dp[-1][-1]

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

        dp = [j for j in range(len2+1)] # 0, 1, 2, 3...

        for i in range(1, len1+1):
            left = i
            for j in range(1, len2+1):
                # 对应的两个字符相等，什么编辑都不需要做
                # 编辑距离等于 word1[:i-1] 与 word2[:j-1] 的编辑距离
                if word1[i-1] == word2[j-1]:
                    cur = dp[j-1]
                else:
                    top, topleft = dp[j], dp[j-1]
                    cur = min(
                        # 可以通过在 word1[:i] 后插入 w2[j] 变成 word2[:j], 
                        # 那首先至少需要先通过将 word[:i] 编辑成 word2[:j-1]
                        # 因此，编辑距离等于 word1[:i] 与 word2[:j-1]的编辑距离 + 1
                        left + 1, 
                        # 可以通过在 word1[:i] 后删除 w1[i] 变成 word2[:j], 
                        # 那首先至少需要先通过将 word[:i-1] 编辑成 word2[:j]
                        # 因此，编辑距离等于 word1[:i-1] 与 word2[:j]的编辑距离 + 1
                        top + 1,     
                        # 可以通过把 word1[:i] 的 w1[i] 替换成 w2[j] 使其变成 word2[:j], 
                        # 那首先至少需要先通过将 word[:i-1] 编辑成 word2[:j-1]
                        # 因此，编辑距离等于 word1[:i-1] 与 word2[:j-1]的编辑距离 + 1
                        topleft + 1,                            
                    )
                dp[j-1], left = left, cur
            dp[-1] = left

        return dp[-1]

"""
"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        self.head, self.pre = None, None

        def inorder(cur):
            if not cur: return 
            inorder(cur.left)
            if not self.pre:
                # 如果 self.pre 没有值
                # 说明没有左子树可以遍历
                # 当前节点是链表的头结点（整棵树的最左边叶子，最小值）
                self.head = cur
            else:
                self.pre.right, cur.left = cur, self.pre
            self.pre = cur

            # 中序遍历，会先访问到右子树的最左节点
            # 然后与 self.pre (也就是 cur) 进行连接
            inorder(cur.right)

        if not root: return None
        inorder(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

class Solution:
    def twoSum(self, n: int) -> List[float]:
        dp = [[0] * (6*n+1) for _ in range(n+1)] # dp[0...n][0...6*n]

        for cur in range(1, 7):
            dp[1][cur] = 1
        

        for i in range(2, n+1):
            for s in range(i, i*6+1): # i 个骰子的点数最小为 i，最大是 6*i
                for cur in range(1, 7):
                    if s - cur > 0:
                        dp[i][s] += dp[i-1][s-cur]
        
        all = math.pow(6, n)
        res = []
        for s in range(n, 6*n+1):
            res.append(dp[n][s] / all)
        return res

class Solution:
    def twoSum(self, n: int) -> List[float]:
        dp = [[0] * (6*n+1) for _ in range(n+1)] # dp[0...n][0...6*n]

        dp = [0] * (6*n+1)

        for cur in range(1, 7):
            dp[cur] = 1
        
        for i in range(2, n+1):
            for s in range(i*6, i-1, -1):
                dp[s] = 0 # 每次更新需要重新计算，s只与 s-1 ... s-6有关
                for cur in range(1, 7):
                    if s - cur >= i - 1: # 前i-1 个骰子不可能抛出小于 i-1 的点数
                        dp[s] += dp[s-cur]
        
        all = math.pow(6, n)
        res = []
        for s in range(n, 6*n+1):
            res.append(dp[s] / all)
        return res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return 
        root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
        return root

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def find_kth(k):
            n1, n2 = len(nums1), len(nums2)

            idx1, idx2 = 0, 0

            while True:
                # nums1 或 nums2 比较完了
                if idx1 == n1: return nums2[idx2+k-1]
                if idx2 == n2: return nums1[idx1+k-1]
                # 如果 k == 1，那下一个数就是要找的数
                # 在 idx1 和 idx2 中取最小的
                if k == 1: return min(nums1[idx1], nums2[idx2])

                # 正常情况
                # 每个 nums 取 idx...idx + k//2 - 1，分别考察 k//2 个数
                new_idx1 = min(idx1 + k//2 - 1, n1 - 1)
                new_idx2 = min(idx2 + k//2 - 1, n2 - 1)

                # 如果 nums1[new_idx1] <= nums2[new_idx2], 说明至少可以排除掉
                # 至多有 (k//2 - 1) * 2 = k - 2 个数比 nums1[new_idx1] 小
                # nums[idx1] 最多是第 k-1 个数，肯定不是第 k 个数
                # 因此可以排除掉刚刚考察的 k//2 个 nums1 中的数，nums[idx1...new_idx1]
                # 他们肯定都比第 k 个数小
                if nums1[new_idx1] <= nums2[new_idx2]:
                    # 已经排除掉 nums1 中的那些数字了
                    # 只需要在剩下的数字里找一个更小第k位数
                    k -= new_idx1 - idx1 + 1
                    idx1 = new_idx1 + 1
                else:
                    k -= new_idx2 - idx2 + 1
                    idx2 = new_idx2 + 1

        N = len(nums1) + len(nums2)

        if N & 1: return find_kth(N + 1 >> 1)
        else: return 0.5 * (find_kth(N >> 1) + find_kth((N >> 1) + 1))