# O(n) time | O(1) space
def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# Two Pointers — check if pair sums to target (sorted array)
def two_sum_sorted(arr, target):
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if s == target: return l, r
        elif s < target: l += 1
        else: r -= 1
    return -1, -1

class Node:
    def __init__(self, val): self.val = val; self.next = None

# O(n) time | O(1) space — iterative (preferred in interviews)
def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next  # save next
        curr.next = prev  # reverse pointer
        prev = curr       # advance prev
        curr = nxt        # advance curr
    return prev  # new head

# Floyd's Cycle Detection — O(n) time, O(1) space
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: return True
    return False

def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in mapping:
            top = stack.pop() if stack else '#'
            if mapping[ch] != top: return False
        else: stack.append(ch)
    return not stack  # O(n) time | O(n) space

# Monotonic Stack — Next Greater Element
def next_greater(nums):
    res = [-1] * len(nums); stack = []
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            res[stack.pop()] = n
        stack.append(i)
    return res

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

# In-order (yields sorted output for BST)
def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

# Validate BST — O(n) time, O(h) space
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root: return True
    if not (lo < root.val < hi): return False
    return is_valid_bst(root.left,lo,root.val) and is_valid_bst(root.right,root.val,hi)

# Max Depth — O(n)
def max_depth(root):
    return 0 if not root else 1 + max(max_depth(root.left), max_depth(root.right))

from collections import deque

# BFS — shortest path in unweighted graph
def bfs(graph, start):
    visited = {start}; q = deque([start])
    while q:
        node = q.popleft()
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr); q.append(nbr)

# DFS — iterative (avoid recursion limit)
def dfs(graph, start):
    visited = set(); stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        stack.extend(graph[node])

# Number of Islands — classic DFS on grid
def num_islands(grid):
    count = 0
    def sink(r, c):
        if not (0<=r<len(grid) and 0<=c<len(grid[0]) and grid[r][c]=='1'): return
        grid[r][c] = '0'
        for dr,dc in [(0,1),(0,-1),(1,0),(-1,0)]: sink(r+dr,c+dc)
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c]=='1': sink(r,c); count += 1
    return count

from collections import Counter, defaultdict

# Two Sum — O(n) time, O(n) space
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen: return [seen[complement], i]
        seen[n] = i

# Group Anagrams — O(nk log k) time
def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs: groups[tuple(sorted(s))].append(s)
    return list(groups.values())

# Longest Consecutive Sequence — O(n) time with set
def longest_consecutive(nums):
    num_set = set(nums); longest = 0
    for n in num_set:
        if n-1 not in num_set:  # start of sequence
            length = 1
            while n+length in num_set: length += 1
            longest = max(longest, length)
    return longest

# Merge Sort — O(n log n) guaranteed, O(n) space
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    L, R = merge_sort(arr[:mid]), merge_sort(arr[mid:])
    i = j = 0; res = []
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: res.append(L[i]); i += 1
        else: res.append(R[j]); j += 1
    return res + L[i:] + R[j:]

# Quick Sort — O(n log n) avg, O(n²) worst (bad pivot)
def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return
    pivot = arr[hi]; i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1; arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    p = i + 1
    quick_sort(arr, lo, p-1); quick_sort(arr, p+1, hi)

# Standard — exact match
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

# Search on answer space — minimum valid answer
def search_answer(lo, hi, feasible):
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else: lo = mid + 1
    return lo  # minimum satisfying value

# Coin Change — min coins to make amount. O(n×amount)
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1); dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# Longest Common Subsequence — O(nm) time and space
def lcs(s, t):
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            dp[i][j] = dp[i-1][j-1] + 1 if s[i-1]==t[j-1] else max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]