def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    # Left pass: result[i] = product of all elements left of i
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    # Right pass: multiply by product of all elements right of i
    suffix = 1
    for i in range(n-1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

# Time: O(n), Space: O(1) — no division!

def lengthOfLongestSubstring(s):
    char_index = {}  # char -> last seen index
    max_len = 0
    left = 0
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1  # shrink window
        char_index[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

# Time: O(n), Space: O(min(m,n)) where m = charset size

from collections import Counter

def minWindow(s, t):
    need = Counter(t)
    have, total_needed = 0, len(need)
    window = {}
    result = ""
    min_len = float('inf')
    left = 0

    for right, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1

        while have == total_needed:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right+1]
            # Shrink window from left
            window[s[left]] -= 1
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1
            left += 1

    return result

# Time: O(|s|+|t|), Space: O(|s|+|t|)

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        key = tuple(sorted(word))  # sorted chars as key
        groups[key].append(word)
    return list(groups.values())

# Alternative: use Counter as key (need frozenset)
# Time: O(n * k log k) where k = max string len
# Space: O(n * k)

def maxArea(height):
    l, r = 0, len(height) - 1
    max_water = 0
    while l < r:
        water = min(height[l], height[r]) * (r - l)
        max_water = max(max_water, water)
        # Move the shorter pointer inward (greedy)
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return max_water

# Time: O(n), Space: O(1)

def trap(height):
    l, r = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while l <= r:
        if height[l] <= height[r]:
            if height[l] >= left_max:
                left_max = height[l]
            else:
                water += left_max - height[l]
            l += 1
        else:
            if height[r] >= right_max:
                right_max = height[r]
            else:
                water += right_max - height[r]
            r -= 1
    return water

# Time: O(n), Space: O(1)
# Key: water at position = min(left_max, right_max) - height[i]

from collections import deque

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

# Template for ALL level-order problems
# Time: O(n), Space: O(n)

# Binary Tree LCA (general)
def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left  = lowestCommonAncestor(root.left,  p, q)
    right = lowestCommonAncestor(root.right, p, q)
    # If both subtrees return non-null, root is LCA
    if left and right:
        return root
    return left or right

# BST LCA (use BST property)
def lcaBST(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root  # split point = LCA

def isValidBST(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if not (min_val < root.val < max_val):
        return False
    return (isValidBST(root.left, min_val, root.val) and
            isValidBST(root.right, root.val, max_val))

# Key: pass bounds down the recursion
# NOT just checking left.val < root.val < right.val (wrong!)

from collections import deque

class Codec:
    def serialize(self, root):
        if not root: return "null"
        result = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")
        return ",".join(result)

    def deserialize(self, data):
        vals = data.split(",")
        if vals[0] == "null": return None
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

def pathSum(root, targetSum):
    result = []
    def dfs(node, remaining, path):
        if not node: return
        path.append(node.val)
        # Leaf node and sum matches
        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])  # snapshot of path
        else:
            dfs(node.left,  remaining - node.val, path)
            dfs(node.right, remaining - node.val, path)
        path.pop()  # backtrack
    dfs(root, targetSum, [])
    return result

def numIslands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited (in-place)
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

# Time: O(m*n), Space: O(m*n) recursion stack

from collections import deque

def cloneGraph(node):
    if not node: return None
    cloned = {}  # original -> clone
    cloned[node] = Node(node.val)
    queue = deque([node])

    while queue:
        curr = queue.popleft()
        for neighbor in curr.neighbors:
            if neighbor not in cloned:
                cloned[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            cloned[curr].neighbors.append(cloned[neighbor])

    return cloned[node]

# Key: map original node to its clone
# Time: O(V+E), Space: O(V)

from collections import deque

def canFinish(numCourses, prerequisites):
    # Build adjacency list + in-degree array
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    # Kahn's Algorithm (BFS topological sort)
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    completed = 0
    while queue:
        course = queue.popleft()
        completed += 1
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return completed == numCourses  # False if cycle exists

# DFS approach (also valid):
# State: 0=unvisited, 1=visiting(in stack), 2=visited
# If visit a node with state=1 → cycle detected

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set: return 0

    queue = deque([(beginWord, 1)])  # (word, steps)
    visited = {beginWord}

    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word == endWord:
                    return steps + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))
    return 0

# BFS guarantees shortest path

def pacificAtlantic(heights):
    rows, cols = len(heights), len(heights[0])
    pacific = set(); atlantic = set()

    def bfs(starts, visited):
        queue = deque(starts)
        visited.update(starts)
        while queue:
            r, c = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = r+dr, c+dc
                if (0 <= nr < rows and 0 <= nc < cols and
                    (nr,nc) not in visited and
                    heights[nr][nc] >= heights[r][c]):
                    visited.add((nr,nc))
                    queue.append((nr,nc))

    pacific_starts = [(0,c) for c in range(cols)] + [(r,0) for r in range(rows)]
    atlantic_starts = [(rows-1,c) for c in range(cols)] + [(r,cols-1) for r in range(rows)]
    bfs(pacific_starts, pacific)
    bfs(atlantic_starts, atlantic)
    return list(pacific & atlantic)  # intersection

def climbStairs(n):
    if n <= 2: return n
    dp_prev2, dp_prev1 = 1, 2
    for _ in range(3, n+1):
        dp_prev2, dp_prev1 = dp_prev1, dp_prev1 + dp_prev2
    return dp_prev1
# Fibonacci pattern: f(n) = f(n-1) + f(n-2)

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins to make 0
    for amt in range(1, amount + 1):
        for coin in coins:
            if coin <= amt:
                dp[amt] = min(dp[amt], dp[amt - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# Time: O(amount * len(coins)), Space: O(amount)
# dp[i] = min coins to make amount i

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]

# Time: O(m*n), Space: O(m*n)
# Recurrence:
# if match: dp[i][j] = dp[i-1][j-1] + 1
# else:     dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n+1)
    dp[0] = True  # empty string is always segmentable

    for i in range(1, n+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

# Time: O(n^2), Space: O(n)

def longestPalindrome(s):
    result = ""
    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]  # valid palindrome

    for i in range(len(s)):
        odd  = expand(i, i)    # odd length
        even = expand(i, i+1)  # even length
        if len(odd)  > len(result): result = odd
        if len(even) > len(result): result = even
    return result

# Time: O(n^2), Space: O(1)

# Iterative
def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

# Recursive
def reverseListRec(head):
    if not head or not head.next:
        return head
    new_head = reverseListRec(head.next)
    head.next.next = head
    head.next = None
    return new_head

def detectCycle(head):
    slow = fast = head
    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle

    # Phase 2: Find cycle start
    # Move one pointer to head, advance both 1 step at a time
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow  # meeting point = cycle start

import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    curr = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# Time: O(N log k) where N=total nodes, k=number of lists

import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    # nlargest: uses heap internally O(n log k)
    return heapq.nlargest(k, count.keys(), key=count.get)

# Alternative: Bucket Sort O(n)
def topKFrequentBucket(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums)+1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for i in range(len(buckets)-1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
    return result

import heapq

def kClosest(points, k):
    # Use max-heap of size k (negate distance)
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

# Or simpler: sort by distance
def kClosestSimple(points, k):
    points.sort(key=lambda p: p[0]**2 + p[1]**2)
    return points[:k]

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap (negate) — left half
        self.large = []  # min-heap — right half

    def addNum(self, num):
        heapq.heappush(self.small, -num)
        # Ensure max of small <= min of large
        if self.small and self.large and (-self.small[0] > self.large[0]):
            heapq.heappush(self.large, -heapq.heappop(self.small))
        # Balance sizes
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

# Classic binary search
def binarySearch(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2  # avoid overflow
        if nums[mid] == target: return mid
        elif nums[mid] < target: l = mid + 1
        else: r = mid - 1
    return -1

# Find first/last position
def searchRange(nums, target):
    def find_bound(is_left):
        l, r = 0, len(nums) - 1
        bound = -1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                bound = mid
                if is_left: r = mid - 1
                else: l = mid + 1
            elif nums[mid] < target: l = mid + 1
            else: r = mid - 1
        return bound
    return [find_bound(True), find_bound(False)]

# Search in Rotated Sorted Array
def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target: return mid
        # Left half is sorted
        if nums[l] <= nums[mid]:
            if nums[l] <= target < nums[mid]: r = mid - 1
            else: l = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[r]: l = mid + 1
            else: r = mid - 1
    return -1

def isValid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices, front = max element's index
    result = []
    for i, n in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order (remove smaller elements from back)
        while dq and nums[dq[-1]] < n:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Time: O(n), Space: O(k)
# Key: monotonic decreasing deque