# Brute Force
def max_subarray_sum(arr):
    max_sum = float('-inf')
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            current_sum = sum(arr[i:j+1])
            max_sum = max(max_sum, current_sum)
    return max_sum

# sliding window O(n)
def maxSubArray(self, nums: List[int]) -> int:
    left = 0
    right = 0
    n = len(nums)
    cur = nums[left]
    m_sum = cur
    while True:
        if cur < 0:
            left = right + 1
            right = left
            cur = 0
            if left >= n:
                break
            cur = nums[left]
        else:
            right += 1
            if right >= n:
                break
            cur += nums[right]
        if cur > m_sum:
            m_sum = cur
    return m_sum

# Kadane's Algorithm O(n)
def kadanes(nums):
  max_sum = nums[0]
  cur_sum = 0
  for n in nums:
    cur_sum = max(0, cur_sum)
    cur_sum += n
    max_sum = max(max_sum, cur_sum)
  return max_sum

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    max_sw = []
    left, right = 0, 0
    n = len(nums) 
    while right < n:
        e_r = nums[right]
        if e_r in win:
            win[e_r] += 1
        else:
            win[e_r] = 1
        if right - left + 1 == k:
            max_sw.append(max(win))
            e_l = nums[left]
            if win[e_l] > 1:
                win[e_l] -= 1
            else:
                del win[e_l]
            left += 1
        right += 1
    return max_sw

dq = deque()   # stores indices
result = []
for i in range(len(nums)):
    # 1️⃣ Remove indices out of window
    if dq and dq[0] == i - k:
        dq.popleft()
    # 2️⃣ Maintain decreasing order
    while dq and nums[dq[-1]] < nums[i]:
        dq.pop()
    # 3️⃣ Add current index
    dq.append(i)
    # 4️⃣ Window formed
    if i >= k - 1:
        result.append(nums[dq[0]])
return result

def targerSum(nums, target):
  L,R = 0, len(nums) - 1
  while L < R:
    if nums[L] + nums[R] > target:
      R -= 1
    elif nums[L] + nums[R] < target:
      L += 1
    else:
      return [L, R]

class prefix_sum:
    def __init__(self, nums):
        self.prefix = []
        total = 0
        for n in nums:
            total += n
            self.prefix.append(total)
    
    def subsum(self, left, right):
        pre_right = self.prefix[right]
        pre_left = self.prefix[left-1] if left > 0 else 0
        return pre_right - pre_left

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    prefix, suffix = [1], [1]
    result = []
    for i in range(n-1):
        prefix.append(prefix[-1] * nums[i])
        suffix.append(suffix[-1] * nums[n-1-i])
    for i in range(n):
        result.append(prefix[i] * suffix[n-i-1])
    return result

# Or we can allocate the memory first
def productExceptSelf(self, nums: List[int]) -> List[int]:
    result = [1] * len(nums)
    right, left = 1, 1
    for i in range(len(nums)):
        result[i] *= left
        left *= nums[i]
    for i in range(len(nums)-1, -1, -1):
        result[i] *= right
        right *= nums[i]
    return result 

def middle_of_list(head):
    # odd and even case are both covered by this algorithm, when there are two middle nodes, the slow pointer will jump over the first middle node and stop at the second middle node.
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

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

def find_cycle_entry(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    if not fast or not fast.next:
        return None
    entry = head
    while entry != slow:
        entry = entry.next
        slow = slow.next
    return entry

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.word = True

    def search(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.word
    
    def startsWith(self, prefix):
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return True

class UnionFind:
    def __init__(self, n):
		# each node is its own parent initially
        self.parent = [i for i in range(n)]
		# weight[i] is the size of the tree rooted at i
		self.weight = [1] * n

	def find(self, x):
		if self.parent[x] != x:
			# path compression
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		rootX = self.find(x)
		rootY = self.find(y)
        if rootX == rootY:
            return False
		if rootX != rootY:
			# attach the small tree to the bigger one
			if self.weight[rootX] > self.weight[rootY]:
				self.parent[rootY] = rootX
				self.weight[rootX] += self.weight[rootY]
			else:
				self.parent[rootX] = rootY
				self.weight[rootY] += self.weight[rootX]
        return True

	def build(self, edges):
		"""Build the union-find structure from the edges of the graph.
		The complexity of this function is O(m*α(n)), 
		where m is the number of edges and n is the number of nodes.
		α(n) present the time complexity of find function, 
		which is very slow growing and
		can be considered as a constant for all practical purposes with path compression
		and union by weight.
		So the overall complexity of this function can be considered as O(m).
		"""
		for x, y in edges:
			self.union(x, y)

	def connected(self, x, y):
		"""Check if two nodes are connected.
		"""
		return self.find(x) == self.find(y)

	def count_components(self):
		"""Count the number of connected components in the graph.
		"""
		roots = set()
		for i in range(len(self.parent)):
			roots.add(self.find(i))
		return len(roots)
	
	def cycle_detection(self, edges):
		"""Detect if there is a cycle in the graph. If there is a cycle, return True, otherwise return False.
		"""
		for x, y in edges:
			if self.connected(x, y):
				return True
			self.union(x, y)
		return False

class SegmentTree:
    """ simple segment tree implementation for sum operation"""
    def __init__(self, total, l_b, r_b):
        """
        Args
            total: total sum
            l_b: left bound
            r_b: right bound
        """
        self.sum = total
        self.left = None
        self.right = None
        self.l_b = l_b
        self.r_b = r_b
    
    @staticmethod
    def build(nums, l_b, r_b):
        """ build the segment tree with O(n) with n is 
            the number of nodes and n is the number of leafs
        """
        if l_b == r_b:
            return SegmentTree(nums[l_b], l_b, r_b)
        m = (l_b + r_b) // 2
        root = SegmentTree(0, l_b, r_b)
        root.left = SegmentTree.build(nums, l_b , m)
        root.right = SegmentTree.build(nums, m + 1, r_b)
        root.sum = root.left.sum + root.right.sum
        return root

    def update(self, index, val):
        if self.l_b == self.r_b:
            self.sum = val
            return
        m = (self.l_b + self.r_b) // 2
        if index > m:
            self.right.update(index, val)
        else:
            self.left.update(index, val)
        self.sum = self.left.sum + self.right.sum

    # The time complexity of this function is O(log n) where n is the number of leaf nodes in the segment tree, which is the same as the number of elements in the original array. This is because in each step of the recursion, we are halving the range of the query, and we will have at most log n levels of recursion until we reach the leaf nodes.
    def range_query(self, l_b, r_b):
        if l_b == self.l_b and r_b == self.r_b:
            return self.sum
        m = (self.l_b + self.r_b) // 2
        if l_b > m:
            return self.right.range_query(l_b, r_b)
        elif r_b <= m:
            return self.left.range_query(l_b, r_b)
        else:
            return (self.left.range_query(l_b, m) +
                    self.right.range_query(m + 1, r_b))

class TreeNode:
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right

def inorder(root):
    # time and space o(n), space complexity is due to the inbalance case.
    stack = []
    cur = root
    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            print(cur.val)
            cur = cur.right

def preorder(root):
    stack = []
    cur = root
    while cur or stack:
        if cur:
            print(cur.val)
            if cur.right:
                stack.append(cur.right)
            cur = cur.left
        else:
            cur = stack.pop()

def postorder(root):
    # The key idea is that the we do not print the first visit 
    # only print the parent when ths fist and second children 
    # have been passed
    stack = [root]
    visit = [False]
    while stack:
        cur, visited = stack.pop(), visit.pop()
        if cur:
            if visited:
                print(cur.val)
            else:
                stack.append(cur)
                visit.append(True)
                stack.append(cur.right)
                visit.append(False)
                stack.append(cur.left)
                visit.append(False)

import heapq

class TwoHeapMedianFinder:
    def __init__(self):
        self.small = []  # max heap
        self.large = []  # min heap

    def insert(self, num: int) -> None:
        """ Heap insertion """
        # push first to the small max heap and push to large min heap if needed
        heapq.heappush(self.small, -num)
        if self.small and self.large and (-self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)

        # Uneven size handle
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        if len(self.large) > len(self.small) + 1:
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

    def get_median(self):
        """ Heap get minimum """
        l_s, l_l = len(self.small), len(self.large)
        if l_s > l_l:
            return -self.small[0]
        elif l_s < l_l:
            return self.large[0]
        else:
            return (-self.small[0] + self.large[0]) // 2

def subsets_without_dup(nums):
    cur_set, subsets = [], []
    helper(0, nums, cur_set, subsets)
    return subsets

def helper(i, nums, cur_set, subsets):
    if i >= len(nums):
        subsets.append(cur_set.copy())
        return
    # decision to include nums[i]
    cur_set.append(nums[i])
    helper(i + 1, nums, cur_set, subsets)

    # this step is the kernel of backtracking
    cur_set.pop()

    # decision to not include nums[i]
    helper(i + 1, nums, cur_set, subsets)

def subsets_without_dup(nums):
    nums.sort()  # sort the array to handle duplicates
    cur_set, subsets = [], []
    helper(0, nums, cur_set, subsets)
    return subsets

def helper(i, nums, cur_set, subsets):
    if i >= len(nums):
        subsets.append(cur_set.copy())
        return
    # decision to include nums[i]
    cur_set.append(nums[i])
    helper(i + 1, nums, cur_set, subsets)
    # this step is the kernel of backtracking
    cur_set.pop()

    # decision to not include nums[i]
    while i + 1 < len(nums) and nums[i] == nums[i + 1]:
        i += 1
    helper(i + 1, nums, cur_set, subsets)

def combination(n, k):
    cur_set, subsets = [], []
    helper(0, n, k, cur_set, subsets)
    return subsets

def helper(i, n, k, cur_set, subsets):
    if len(cur_set) == k:
        subsets.append(cur_set.copy())
        return
    if i >= n:
        return
    cur_set.append(i+1) # the number
    helper(i + 1, n, k, cur_set, subsets)
    cur_set.pop()
    helper(i + 1, n, k, cur_set, subsets)

# Combinations II: Use the combination logic, we start with n choice and then we have n-1 choice and then n-2 choice, until we have k choice. So we can use the same backtracking logic as combination, but we need to add a condition to skip the numbers that are already in the current set. This way we can avoid generating duplicate combinations.
def combination2(n, k):
    cur_set, subsets = [], []
    helper2(0, n, k, cur_set, subsets)
    return subsets

def helper2(i, n, k, cur_set, subsets):
    if len(cur_set) == k:
        subsets.append(cur_set.copy())
        return
    if i >= n:
        return

    for j in range(i + 1, n + 1):
        cur_set.append(j)
        helper2(j, n, k, cur_set, subsets)
        cur_set.pop()

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        perms = []
        n = len(nums)
        self.helper(nums, n, [], perms)
        return perms

    def helper(self, nums, n, cur_perm, perms):
        if len(cur_perm) == n:
            perms.append(cur_perm)
            return 
        for j, num in enumerate(nums):
            new_perm = cur_perm + [num]
            nums_rest = nums[:j] + nums[j + 1:]
            self.helper(nums_rest, n, new_perm, perms)

import heapq

def shortest_path(edges, n, src):
    adj = {}
    for i in range(1, n + 1):
        adj[i] = []
    for s, d, w in edges:
        # source, destinatio, weights
        adj[s].append((d, w))
    shortest = {}
    # a head of (weigh, destination)
    min_heap = [(0, src)]
    while min_heap:
        w1, n1 = heapq.heappop(min_heap)
        if n1 in shortest:
            continue
        shortest[n1] = w1
        for n2, w2 in adj[n1]:
            if n2 not in shortest:
                # distance from src update
                heapq.heappush(min_heap, (w1 + w2, n2))
    return shortest

import heapq

def min_spanning_tree(edges, n):
    # construct the adjacent dictionary
    adj = {}
    for i in range(1, n + 1):
        adj[i] = []
    for src, dst, weight in edges:
        adj[src].append([dst, weight])
        adj[dst].append([src, weight])

    # Initialise the heap by chosing a single node
    # pushing all its neighbours
    min_heap = []
    for neighbor, weight in adj[1]:
        heapq.heappush(min_heap, [weight, 1, neighbor])
    mst = [] # min spinning tree result
    visited = set()
    visited.add(1)

    while min_heap:
        weight, src, node = heapq.heappop(min_heap)
        if node in visited:
            continue
        mst.append([src, node])
        visited.add(node)
        for neighbor, weight in adj[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, [weight, node, neighbor])
    return mst

def min_spanning_tree_kruskal(edges, n):
    # sort the edges by weight
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    for src, dst, weight in edges:
        if uf.union(src, dst):
            mst.append([src, dst])
        if len(mst) == n - 1:
            break
    return mst

def topological_sort(edges, n):
    adj = {}
    for i in range(1, n + 1):
        adj[i] = []
    for src, dst in edges:
        adj[src].append(dst)
    
    top_sort = []
    visited = set()
    for i in range(1, n + 1):
        dfs(i, adj, visited, top_sort)
    top_sort.reverse()
    return top_sort

def dfs(src, adj, visited, top_sort):
    if src in visited:
        return
    visited.add(src)
    for dst in adj[src]:
        dfs(dst, adj, visited, top_sort)
    top_sort.append(src)

def dfs(profit, weight, capacity):
    return dfs_helper(0, profit, weight, capacity)

def dfs_helper(i, profit, weight, capacity):
    if i == len(profit):
        return 0
    # skip the item i
    max_profit  = dfs_helper(i + 1, profit, weight, capacity)
    # include the item i
    new_capacity = capacity - weight[i]
    if new_capacity >= 0:
        max_profit = max(max_profit, profit[i] + dfs_helper(i + 1, profit, weight, new_capacity))
    return max_profit

def memory_dfs(profit, weight, capacity):
    # given the number of items we treated and the remain capacity
    # we can decide the max_profit, so this result can be reuse
    n, m = len(profit), capacity
    cache = [[-1] * (m+1) for _ in range(n)]
    return memory_helper(0, profit, weight, capacity, cache)

def memory_helper(i, profit, weight, capacity, cache):
    if i == len(profit):
        return 0
    elif cache[i][capacity] != -1:
        return cache[i][capacity]
    # skip the item i
    cache[i][capacity]  = memory_helper(i + 1, profit, weight, capacity, cache)
    # include the item i
    new_capacity = capacity - weight[i]
    if new_capacity >= 0:
        cache[i][capacity] = max(
            cache[i][capacity],
            profit[i] + memory_helper(i + 1, profit, weight, new_capacity, cache))
    return cache[i][capacity]

def dp(profit, weight, capacity):
    n = len(profit)
    dp_table = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for c in range(capacity + 1):
            dp_table[i][c] = dp_table[i - 1][c]
            if weight[i - 1] <= c:
                dp_table[i][c] = max(
                    dp_table[i][c],
                    profit[i - 1] + dp_table[i - 1][c - weight[i - 1]]
                )
    return dp_table[n][capacity]

def dfs(profit, weight, capacity):
    return dfs_helper(0, profit, weight, capacity)

def dfs_helper(i, profit, weight, capacity):
    if i == len(profit):
        return 0
    # skip the item i
    max_profit  = dfs_helper(i + 1, profit, weight, capacity)
    # include the item i
    new_capacity = capacity - weight[i]
    if new_capacity >= 0:
        # here we set i instead of i + 1 because we can include the same item multiple times
        p = profit[i] + dfs_helper(i, profit, weight, new_capacity)
        max_profit = max(max_profit, p)
    return max_profit

def memory_dfs(profit, weight, capacity):
    # given the number of items we treated and the remain capacity
    # we can decide the max_profit, so this result can be reuse
    n, m = len(profit), capacity
    cache = [[-1] * (m+1) for _ in range(n)]
    return memory_helper(0, profit, weight, capacity, cache)

def memory_helper(i, profit, weight, capacity, cache):
    if i == len(profit):
        return 0
    elif cache[i][capacity] != -1:
        return cache[i][capacity]
    # skip the item i
    cache[i][capacity]  = memory_helper(i + 1, profit, weight, capacity, cache)
    # include the item i
    new_capacity = capacity - weight[i]
    if new_capacity >= 0:
        cache[i][capacity] = max(
            cache[i][capacity],
            # Here is the key difference from the knapsack problem, we can include the same item multiple times, so we do not move to the next item after including the current item.
            profit[i] + memory_helper(i, profit, weight, new_capacity, cache))
    return cache[i][capacity]

def dp(profit, weight, capacity):
    n = len(profit)
    dp_table = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for c in range(capacity + 1):
            dp_table[i][c] = dp_table[i - 1][c]
            if weight[i - 1] <= c:
                dp_table[i][c] = max(
                    dp_table[i][c],
                    # use dp_table[i] instead of dp_table[i-1] to allow reusing item i
                    profit[i - 1] + dp_table[i][c - weight[i - 1]]
                )
    return dp_table[n][capacity]

def fds(text1, text2):
    return helper(text1, text2, 0, 0)

def helper(text1, text2, i1, i2):
    if i1 == len(text1) or i2 == len(text2):
        return 0
    if text1[i1] == text2[i2]:
        return 1 + helper(text1, text2, i1+1, i2+1)
    else:
        return max(
            self.helper(text1, text2, i1+1, i2),
            self.helper(text1, text2, i1, i2+1)
        )

def memory_dfs(text1, text2):
    m, n = len(text1), len(text2)
    cache = [[-1] * n for _ in range(m)]
    return helper(text1, text2, 0, 0, cache)

def helper(text1, text2, i1, i2, cache):
    if i1 == len(text1) or i2 == len(text2):
        return 0
    elif cache[i1][i2] != -1:
        return cache[i1][i2]
    if text1[i1] == text2[i2]:
        cache[i1][i2] = 1 + helper(text1, text2, i1+1, i2+1, cache)
    else:
        cache[i1][i2] = max(
            helper(text1, text2, i1+1, i2, cache),
            helper(text1, text2, i1, i2+1, cache)
        )
    return cache[i1][i2]

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

def longestPalindrome(s: str) -> str:
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1
    start, end = 0, 0
    for i in range(len(s)):
        # odd
        l1, r1 = expand(i, i)
        # even
        l2, r2 = expand(i, i + 1)
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2
    return s[start:end + 1]