class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [ i^(i>>1) for i in range(2**n) ]

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        diff = [ abs(num - x) for num in arr ]
        print(diff)
        rank = [i[0] for i in sorted(enumerate(diff), key=lambda x:x[1])]
        print(rank)
        return sorted([ arr[id] for id in rank[0:k] ])

# This is still wrong! Some cases fail
class Solution:
    
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if not matrix:
            return 0
        
        m = len(matrix)
        n = len(matrix[0])
        ans = -sys.maxsize
        
        for i in range(m):
            for j in range(n):
                matrix[i][j] += matrix[i][j-1]
        for i1 in range(n):
            for i2 in range(i1,n):
                for j1 in range(m):
                    for j2 in range(j1,m):
                        boxSum = matrix[j2][i2]
                        if i1>0: boxSum -= matrix[j1][i1]
                        # if boxSum == k:
                        #     return k
                        
                        if ((boxSum<k) and (abs(k-boxSum) < abs(k-ans))):
                            ans = boxSum
        return ans

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[1, 1, 1, 1, 1]]
# Each vowel 'a' may only be followed by an 'e'.
# Each vowel 'e' may only be followed by an 'a' or an 'i'.
# Each vowel 'i' may not be followed by another 'i'.
# Each vowel 'o' may only be followed by an 'i' or a 'u'.
# Each vowel 'u' may only be followed by an 'a'.        
        for i in range(1, n):
            dp.append([0, 0, 0, 0, 0])
            dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4]
            dp[i][1] = dp[i-1][0] + dp[i-1][2]
            dp[i][2] = dp[i-1][1] + dp[i-1][3]
            dp[i][3] = dp[i-1][2]
            dp[i][4] = dp[i-1][2] + dp[i-1][3]
        return sum(dp[n-1])%(10**9 + 7)

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:        
        m = len(mat)
        n = len(mat[0])
        if (m*n != r*c): return mat
        data = []
        for i in range(m):
            data.extend(mat[i])
        print(data)
        M = [[0 for i in range(c)] for j in range(r)]
        for sn, info in enumerate(data):
            M[int(sn/c)][sn%c]  = info
        print(M)
        return M

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        accumulation = 0
        count = 0
        from collections import Counter
        l = len(arr)
        for k, v in {k: v for k, v in sorted(Counter(arr).items(), key=lambda item: item[1], reverse=True)}.items():
            accumulation += v
            count += 1
            if accumulation >= l/2:
                return count 

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        arr = []
        for row in matrix:
            arr.extend(row)
        arr = sorted(arr)
        return arr[k-1]

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0 for j in range(len(nums2))] for i in range(len(nums1))]
        answer = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                if (i == 0 or j == 0):
                    if (nums1[i] == nums2[j]):
                        dp[i][j] = 0+1
                        answer = max(answer, 0+1)
                    else:
                        dp[i][j] = 0
                else:
                    if (nums1[i] == nums2[j]):
                        dp[i][j] = dp[i-1][j-1]+1
                        answer = max(answer, dp[i-1][j-1]+1)
                    else:
                        dp[i][j] = 0
        return answer

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # dp store the length of subsequence
        dp = [1]*len(nums)
        # go from 1 to the end, 0th is base case 1
        for i in range(1, len(nums)):
            # check every possible subsequence so far
            for j in range(i):
                # check if it is increasing
                if nums[i] > nums[j]:
                    # then update the currect max
                    dp[i]=max(dp[j]+1,dp[i])
        return max(dp)  

class Solution:
    # modulo
    mod =  10**9 + 7
    # prepare a def for recursive
    def solve(self,dp,s,i):
        # base case
        if i==len(s):
            return 1
        # over the iteration
        if i> len(s):
            return 0
        
        # already assigned
        if dp[i] != -1:
            return dp[i]
        # hit a wrong 0
        if s[i] == "0":
            dp[i] =0
            return dp[i]
        
        # reading the next one digit
        one = 0
        if s[i] == '*':
            # all 9 choice
            one += (9*self.solve(dp,s,i+1))% self.mod
        else:
            # actual number
            one += self.solve(dp,s,i+1)
            
        # reading the next two digits
        two = 0
        # check the next two digits available
        if  i+1 < len(s):
            # if it ends with *
            if s[i+1]=='*':
                # start with * => **
                # could only be 11-19(9), 21-16(6) => 9+6 = 15
                if s[i]=='*':
                    two += (15*self.solve(dp,s,i+2))% self.mod
                # '1*' => 11-19 (9)
                elif s[i] <'2':
                    two += (9*self.solve(dp,s,i+2))% self.mod
                # "2*" => 21-26 (6)
                elif s[i] == '2':
                    two += (6*self.solve(dp,s,i+2))% self.mod
            # not ends with *
            else:
                # start with * and ends with some thing less than 7
                # could be 13/23, or 15/25 => 2 possibilities
                if s[i] == "*" and s[i+1]<'7':
                    two += (2*self.solve(dp,s,i+2))% self.mod
                # any none * containing numbers
                elif s[i] <'2' or (s[i] == '2' and s[i+1] <'7'):
                    two += self.solve(dp,s,i+2)
        # register the all possibilities of the current reading point
        dp[i] = ((one % self.mod + two % self.mod)%self.mod)
        return dp[i]
                
        
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [-1]*(n+1)
        return self.solve(dp,s,0)

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        import bisect
        self.pointer = 0
        self.median = 0
        self.len = 0
        self.isOdd = False
        self.num_list = []        

    def addNum(self, num: int) -> None:
        bisect.insort(self.num_list, num)
        self.len += 1
        self.isOdd = not self.isOdd
        
    def findMedian(self) -> float:
        # 3 -> 1, 13 -> 6
        # 4->2
        self.pointer = self.len//2
        # odd, get the number directly
        if self.isOdd:
            return self.num_list[self.pointer]
        # even, get the average of two nearest
        else:
            return (self.num_list[self.pointer] + self.num_list[self.pointer-1])/2

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        map_st = dict(zip(s,t))
        map_ts = dict(zip(t,s))
        for i in range(len(s)):
            if map_st[s[i]] != t[i] or map_ts[t[i]] != s[i]:
                return False
        return True

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # binary style
        l,r = 0, len(nums)-1
        
        # get rid of some corner case
        if r==0 or nums[r] > nums[r-1]:
            return r
        if nums[0] > nums[1]:
            return 0
        
        # helper function
        def getMid(l,r):
            return (l+r)//2
        # recursive
        def findPeak(arr, l, r):
            
            mid = getMid(l,r)
            
            # base case
            if (arr[mid] > arr[mid-1]) and (arr[mid] > arr[mid+1]):
                return mid
            # might locate at right
            elif (arr[mid] < arr[mid+1]):
                return findPeak(arr, mid, r)
            # might locate at left
            else:
                return findPeak(arr, l, mid)
            
        return findPeak(nums, l, r)

class Solution:
    def customSortString(self, order: str, str: str) -> str:
        new_str = ""
        suffix = ""
        # prepare a ordered string holder
        order_dict = {}
        # initialize the dictionary from list or iterable
        for o in order:
            order_dict[o] = ""
        # collect all appeared char and those not in `order`
        for s in str:
            if s in order_dict:
                order_dict[s] += s
            else:
                suffix += s
        # put collected things to string
        for k, v in order_dict.items():
            new_str += v
        # make sure to add the suffix
        new_str += suffix
        return new_str

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        import itertools
        count = 0
        for triplet in itertools.combinations(nums, 3):
            triplet = sorted(list(triplet))
            if (triplet[0] + triplet[1] > triplet[2]):
                count += 1
        return count

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        counter = 0
        for i in range(2, len(nums)):
            short1, short2 = 0, i-1
            # keep checking until all combination, then increase i
            while short2 > short1:
                # the short2 is big enough so all the other larger than short1 can fit
                if nums[short1] + nums[short2] > nums[i]:
                    counter += short2 - short1
                    short2 -= 1
                # overall to small, increase the short1 to see if things get better
                else:
                    short1 += 1
        return counter

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        import itertools
        nums.sort()
        answer = [()]
        i =0
        
        for (a,b,c,d) in set([(a,b,c,d) for (a,b,c,d) in itertools.combinations(nums, 4)]):
            
            if target == a+b+c+d:
                answer.append((a,b,c,d))
        answer.pop(0)
        answer = list(set(answer))
        answer = [ list(quadruplets) for quadruplets in answer]
        return answer

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        def kSum(nums: List[int], target: int, k: int) -> List[List[int]]:
            res = []
            # corner case, empty nums, all component too big, or target too big
            if len(nums) == 0 or nums[0] * k > target or target > nums[-1] * k:
                return res
            # base case
            if k == 2:
                return twoSum(nums, target)
            # no need to worry the offset at the end, catched by corner case
            for i in range(len(nums)):
                # skip the duplicate numbers
                if i == 0 or nums[i - 1] != nums[i]:
                    # recursive funciton to reduce the K
                    #   only sending the rest of the nums
                    #   the remaining value of target
                    #   and the reduced k
                    for set in kSum(nums[i + 1:], target - nums[i], k - 1):
                        res.append([nums[i]] + set)
            return res

        def twoSum(nums: List[int], target: int) -> List[List[int]]:
            res = []
            lo, hi = 0, len(nums) - 1
            while (lo < hi):
                sum = nums[lo] + nums[hi]
                # too small or already checked the lo
                if sum < target or (lo > 0 and nums[lo] == nums[lo - 1]):
                    lo += 1
                # too large or already checked the hi
                elif sum > target or (hi < len(nums) - 1 and nums[hi] == nums[hi + 1]):
                    hi -= 1
                # get an answer, march forward, check those pairs in between
                else:
                    res.append([nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
            return res
        
        nums.sort()
        return kSum(nums, target, 4)

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        # get the index of all ones
        ones = []
        for sn,i in enumerate(arr):
            if i == 1:
                ones.append(sn)
        n = len(ones)
        s = len(arr)
        print(ones)
        # check corner cases
        if n == 0:
            # not sure why but it requires this
            return [0,s-1]
        # eliminate possibilities
        if n%3 != 0:
            return [-1,-1]
        
        # make sure each part have equal number of ones
        a, b, c = ones[0], ones[n//3], ones[n*2//3]
        print(a, b, c)
        # start stepping forward until break
        while (c < s and arr[a] == arr[b] and arr[b] == arr[c]):
            a += 1
            b += 1
            c += 1
        # there is an offset so no need to minus 1
        if c == s:
            return [a-1,b]
        # just no way to find the three parts
        else:
            return [-1,-1]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # base case
        if not head:
            return None
        # corner case
        if k == 1:
            return head
        # check if next recursion is needed
        kSizeChecker = head
        for i in range(k):
            if not kSizeChecker:
                return head
            kSizeChecker = kSizeChecker.next
        # start the business
        cur = head
        nxt = None
        # leave a None for the head
        prv = None
        count = 0
        # link the current to the previous node
        while cur and count < k:
            count += 1
            # get next
            nxt=cur.next
            # link the current to previous node
            cur.next=prv
            # move on, for the next loop, current become previous
            prv=cur
            # move on, for the next loop, next become current
            cur=nxt
        # if there is still something after the linked list
        if nxt:
            # the orginal head is now the last, link it to the next recursion returned value
            head.next=self.reverseKGroup(nxt,k)
        # return the last processed node, which is now at the beginning of the linked list
        return prv

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # base case and corner cases
        if root is None:
            return None
        if root.val == p.val or root.val is q.val:
            return root
        
        left = root.left
        right = root.right
        # traverse left and right
        left = Solution.lowestCommonAncestor(self, left, p, q)
        right = Solution.lowestCommonAncestor(self, right, p, q)
        
        # resolve the returned recursion value
        if left is not None and right is not None:
            return root
        if right is None:
            return left
        if left is None:
            return right

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        # Value of current node or parent node.
        parent_val = root.val

        # Value of p
        p_val = p.val

        # Value of q
        q_val = q.val

        # If both p and q are greater than parent
        if p_val > parent_val and q_val > parent_val:    
            return self.lowestCommonAncestor(root.right, p, q)
        # If both p and q are lesser than parent
        elif p_val < parent_val and q_val < parent_val:    
            return self.lowestCommonAncestor(root.left, p, q)
        # We have found the split point, i.e. the LCA node.
        else:
            return root

class Solution:

    def __init__(self, nums: List[int]):
        self.original_nums = nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.original_nums

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        new_list = self.original_nums[:]
        random.shuffle(new_list)
        return new_list     

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        # prepare the boundary so your don't need to worry about corner cases
        dominoes = f'L{dominoes}R'
        length = len(dominoes)
        new_str = ""
        last_direction = 0

        # make move until finding direction
        for i,d in enumerate(dominoes):
            # skip if dot
            if d == '.':
                continue

            # we have to update since hitting non dot

            # calculate the number of the dots
            chunk = i - last_direction - 1 # only the ...
            # first add the starting char
            if last_direction:
                new_str += dominoes[last_direction]
            # now deal with the dots
            if dominoes[last_direction] == dominoes[i]: # L...L or R...R
                new_str += dominoes[last_direction] * chunk
            elif dominoes[last_direction] == 'R' and dominoes[i] == 'L':    
                new_str += 'R' * (chunk//2)
                new_str += '.' * (chunk%2)
                new_str += 'L' * (chunk//2)
            else: # L...R
                new_str += f"{'.'* chunk}"
            last_direction = i
        return new_str

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        left_max, global_max, ans = nums[0], nums[0], 0
        for i in range(1, len(nums)):
            if nums[i] < left_max:
                # only update left_max if the new element is smaller
                # we don't need to update left_max if the new element is larger everytime
                left_max = global_max
                ans = i
            # the new element is larger than left_max
            # but also larger than global_max
            elif nums[i] > global_max:
                # however, we are not sure if the global_max should be the left part
                global_max = nums[i]
        return ans+1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        
        # check corner case and base case, the end of the tree
        if root is None:
            return None
        
        # traverse
        root.left = Solution.pruneTree(self, root.left)
        root.right = Solution.pruneTree(self, root.right)
        
        # resolve operation
        if (root.val == 0 and root.left is None and root.right is None):
            return None
        return root

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # corner case
        if beginWord == endWord: return [beginWord]
        
        # init
        alphabet = "abcdefghijklmnopqrstuvwxyz"
        wordList = set(wordList)
        q = collections.deque([[beginWord, []]])
        answer = []
        
        # find all shortest path
        while q:
            # unpack value, one by a time
            current_word, path = q.popleft()
            # eliminate duplication possibility
            if current_word in wordList:
                wordList.remove(current_word)
            # resolve cases
            if current_word == endWord:
                # add to answer: no answer yet, or also shortest
                if not answer or len(path)+1 == len(answer[0]):
                    answer.append(path + [current_word])
                # break for path being too long
                elif len(path)+1 > len(answer[0]):
                    break
            # process next word 
            for i in range(len(current_word)):
                for a in alphabet:
                    next_word = f"{current_word[:i]}{a}{current_word[i+1:]}"
                    if next_word in wordList:
                        # add to the queue, don't use append for multiple hits in wordList
                        q.append([next_word, path + [current_word]])
        return answer

class Solution:
    def findIntegers(self, n: int) -> int:
        count = 0
        for i in range(n+1):
            if ((i<<1) & i)==0:
                count += 1
        return count

class Solution:
    def findIntegers(self, n: int) -> int:
        # first get the lengh of the digit
        l = len(format(n,'b'))
        # prepare fibonacci sequence
        fib = [0]*(l+1)
        fib[0] = 1
        fib[1] = 2
        for i in range(2,l+1):
            fib[i] = fib[i-1] + fib[i-2]
        print(fib)
        # init some variables
        isLastBitOne = False # keep track of status
        answer = 0
        bit = l - 1 # offset for the fib
        # accumulate all numbers without Consecutive Ones
        while bit >= 0: # *imagine covering the first digit progressively to fill up need of the longest number*
            if (n & 1<<bit)==0: # current digit not one, means no need to add to answer
                isLastBitOne = False
            else: # current digit is one, means there are some more values need to add to answer
                answer += fib[bit] # add to answer
                if isLastBitOne: # got consecutive ones, all following no matter
                    return answer
                isLastBitOne = True
            bit -= 1 # check next, *imagine covering the first digit*
        return answer+1 # include itself

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums) -> TreeNode:

        l = len(nums)
        # base cases
        if l == 1:
            return TreeNode(nums[0])
        elif l == 0:
            return None
        # traverse the two side
        left = Solution.sortedArrayToBST(self,nums[:l//2])
        right = Solution.sortedArrayToBST(self, nums[l//2+1:])
        # instantiate the current node
        currentNode = TreeNode(nums[l//2], left, right)

        return currentNode

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        diff = sys.maxsize
        answer = 0
        for i in range(len(nums)):
            j = i+1
            k = len(nums)-1
            while k>j:
                tmp = nums[i] + nums[j] + nums[k]
                if tmp == target: return target
                if abs(tmp-target) < diff:
                    diff = abs(tmp-target)
                    answer = tmp
                elif tmp > target:
                    k -= 1
                else:
                    j += 1
        return answer

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        ans = [1]
        while len(ans)<n:
            tmp  =[]
            tmp.extend([i*2-1 for i in ans if (i*2-1)<=n])
            tmp.extend([i*2 for i in ans if (i*2)<=n])
            ans = tmp
        return ans

class Solution:
    def updateMatrix(self, mat):
        from collections import deque
        m = len(mat)
        n = len(mat[0])
        maxsize = m*n
        q = collections.deque()

        def isBoundary(mat, i, j):
            check = False
            if i > 0:
                check = check or mat[i-1][j] == 0
            if j > 0:
                check = check or mat[i][j-1] == 0
            if i < (len(mat)-1):
                check = check or mat[i+1][j] == 0
            if j < (len(mat[0])-1):
                check = check or mat[i][j+1] == 0
            return check

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    continue
                elif isBoundary(mat, i, j):
                    q.append((i, j))
                else:
                    mat[i][j] = maxsize
        while(q):
            (i, j) = q.popleft()
            current_point = mat[i][j]
            current_point_neighbor = [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]
            for (k, l) in current_point_neighbor:
                # no need to change, out of mat or already zero
                if (k not in range(m)) or (l not in range(n)):
                    continue
                elif mat[k][l] == 0:
                    continue
                elif mat[k][l] == maxsize:
                    q.append((k, l))
                # in case there is already a smaller value
                mat[k][l] = min(current_point+1, mat[k][l])
        return mat