Python Coding Interview Prep

from collections import Counter

# A tuple key is a priority order — negate a term to flip that one term's direction
def sort_by_two_keys(pairs):
    pairs.sort(key=lambda x: (x[0], -x[1]))   # x[0] ascending, ties by x[1] descending
    return pairs

# Top K Frequent Elements — Counter already does the sorting
def top_k_frequent(arr, k):
    return [item for item, _ in Counter(arr).most_common(k)]

from functools import cmp_to_key

# Largest Number — arrange digits so the concatenation is the largest possible.
# E.g. [3, 30, 34, 5, 9] → "9534330" (because "3" + "30" > "30" + "3", etc.)
def largest_number(nums):
    arr = [str(x) for x in nums]
    def compare(a, b):
        if a + b > b + a: return -1   # a should come first
        if a + b < b + a: return 1
        return 0
    arr.sort(key=cmp_to_key(compare))
    return ''.join(arr).lstrip('0') or '0'

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    return merge(merge_sort(nums[:mid]), merge_sort(nums[mid:]))

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= keeps the sort stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:])         # exactly one of these two is non-empty
    merged.extend(right[j:])
    return merged

def bubble_sort(nums):              # stable; O(n) best case if you track swaps
    for i in range(len(nums)):
        for j in range(len(nums) - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

def selection_sort(nums):           # NOT stable; always O(n²), minimal writes
    for i in range(len(nums)):
        lo = min(range(i, len(nums)), key=nums.__getitem__)
        nums[i], nums[lo] = nums[lo], nums[i]
    return nums

def insertion_sort(nums):           # stable; O(n) on nearly-sorted input
    for i in range(1, len(nums)):
        cur, j = nums[i], i - 1
        while j >= 0 and nums[j] > cur:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = cur
    return nums

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def find_boundary(nums):                 # first index where condition(nums[i]) holds
    left, right = 0, len(nums) - 1
    result = -1                          # stays -1 when nothing qualifies
    while left <= right:
        mid = (left + right) // 2
        if condition(nums[mid]):
            result = mid                 # a candidate; an earlier one may still exist
            right = mid - 1
        else:
            left = mid + 1
    return result

def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1            # keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

def find_last(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1             # keep searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:                  # left side is the sorted one
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                                        # right side is the sorted one
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

def find_min_rotated(nums):
    left, right = 0, len(nums) - 1
    result = len(nums) - 1               # the last element always qualifies
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] <= nums[-1]:        # at or past the rotation point: a candidate
            result = mid
            right = mid - 1
        else:
            left = mid + 1               # before the rotation point
    return nums[result]

def peak_index(arr):
    left, right = 0, len(arr) - 2        # stop one short so arr[mid + 1] exists
    result = len(arr) - 1                # no descent at all: the last index is the peak
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] > arr[mid + 1]:
            result = mid                 # descending: the peak is mid or to its left
            right = mid - 1
        else:
            left = mid + 1               # still climbing
    return result

def search_matrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    while left <= right:
        mid = (left + right) // 2
        value = matrix[mid // cols][mid % cols]      # flat index → (row, col)
        if value == target:
            return True
        if value < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

# Minimum: the slowest eating speed that still finishes within h hours
def min_eating_speed(piles, h):
    def can_finish(k):
        return sum((p + k - 1) // k for p in piles) <= h     # ceil(p / k) in ints

    left, right = 1, max(piles)
    result = right
    while left <= right:
        mid = (left + right) // 2
        if can_finish(mid):
            result = mid
            right = mid - 1              # feasible: record it, then try smaller
        else:
            left = mid + 1
    return result

# Maximum: the largest x with x * x <= n, i.e. the integer square root
def int_sqrt(n):
    left, right = 0, n
    result = 0
    while left <= right:
        mid = (left + right) // 2
        if mid * mid <= n:
            result = mid
            left = mid + 1               # feasible: record it, then try larger
        else:
            right = mid - 1
    return result

def first_true(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if condition(nums[mid]):
            right = mid          # mid might be the answer — keep it
        else:
            left = mid + 1       # mid is not the answer — skip it
    return left                  # left == right is the answer

def last_true(lo, hi):                   # largest x in [lo, hi] where condition(x) holds
    left, right = lo, hi
    while left < right:
        mid = (left + right + 1) // 2    # upper midpoint, so left = mid always moves
        if condition(mid):
            left = mid
        else:
            right = mid - 1
    return left

# Two Sum in sorted array
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left, right]
        elif s < target: left += 1
        else: right -= 1
    return []

# Remove duplicates from sorted array (in-place)
def remove_duplicates(nums):
    if not nums: return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# Palindrome check
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]: return False
        left += 1
        right -= 1
    return True

# Three Sum — sort, then for each pivot use two pointers
def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]: continue   # skip dup pivot
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]: left += 1
                while left < right and nums[right] == nums[right - 1]: right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result

# Container with most water
def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, min(height[left], height[right]) * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

# Trapping Rain Water — O(n) time, O(1) space
# Water above i depends on min(max_left, max_right). Advance the smaller side:
# its max is the binding constraint, so we know how much water stacks above it.
def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    total = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            total += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            total += right_max - height[right]
            right -= 1
    return total

# Teleporter arrays — two sorted arrays share some values. Between shared values
# you may take either array's run, and at a shared value you may switch sides.
# Accumulate each side's running section sum; at every meeting point commit the
# better of the two and reset both.
def maximum_score(arr1, arr2, mod=10**9 + 7):
    i = j = 0
    sum1 = sum2 = 0
    total = 0

    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            sum1 += arr1[i]; i += 1
        elif arr1[i] > arr2[j]:
            sum2 += arr2[j]; j += 1
        else:                                  # shared value — commit and switch
            total += max(sum1, sum2) + arr1[i]
            sum1 = sum2 = 0
            i += 1
            j += 1

    sum1 += sum(arr1[i:])                      # drain the tails
    sum2 += sum(arr2[j:])
    return (total + max(sum1, sum2)) % mod

# Detect cycle in linked list
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

# Find start of cycle
def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: break
    else:
        return None
    # Reset one pointer to head; both move one step at a time
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

# Find middle of linked list (returns 2nd middle when even length)
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# Find duplicate in array [1..n] (values as next-pointers)
def find_duplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

# Fixed-size window — max sum of k consecutive
def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best

# Variable-size window — longest substring without repeats
def longest_unique_substring(s):
    seen = set()
    left = best = 0
    for right, c in enumerate(s):
        while c in seen:
            seen.remove(s[left])
            left += 1
        seen.add(c)
        best = max(best, right - left + 1)
    return best

# Minimum window substring containing all chars of t
def min_window(s, t):
    from collections import Counter
    from math import inf
    need = Counter(t)
    missing = len(t)
    left = 0
    best_start, best_len = 0, inf

    for right, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1

        if missing == 0:
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            need[s[left]] += 1
            missing += 1
            left += 1

    return "" if best_len == inf else s[best_start:best_start + best_len]

# Longest substring with at most k distinct characters
def longest_k_distinct(s, k):
    from collections import defaultdict
    count = defaultdict(int)
    left = best = 0
    for right, c in enumerate(s):
        count[c] += 1
        while len(count) > k:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

# Longest repeating character replacement — at most k characters may be changed.
# The window is valid when (window length - count of the most common char) <= k,
# i.e. the characters we'd have to overwrite fit inside the budget.
def character_replacement(s, k):
    from collections import defaultdict
    count = defaultdict(int)
    left = best = 0
    for right in range(len(s)):
        count[s[right]] += 1
        while (right - left + 1) - max(count.values()) > k:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

# Shrink-on-duplicate — shortest window containing a repeat.
# Inverts the usual goal: the window is INVALID once a duplicate appears,
# and the answer is recorded at the moment it becomes invalid.
def least_consecutive_cards_to_match(cards):
    seen = set()
    left = 0
    best = len(cards) + 1
    for right in range(len(cards)):
        while cards[right] in seen:
            best = min(best, right - left + 1)
            seen.remove(cards[left])
            left += 1
        seen.add(cards[right])
    return -1 if best > len(cards) else best

# Permutation in String — does s2 contain a permutation of s1?
def check_inclusion(s1, s2):
    if len(s1) > len(s2):
        return False

    need = [0] * 26
    have = [0] * 26
    for i in range(len(s1)):
        need[ord(s1[i]) - ord('a')] += 1
        have[ord(s2[i]) - ord('a')] += 1

    matches = sum(need[i] == have[i] for i in range(26))

    left = 0
    for right in range(len(s1), len(s2)):
        if matches == 26:
            return True

        i = ord(s2[right]) - ord('a')            # character entering
        have[i] += 1
        if have[i] == need[i]:
            matches += 1
        elif have[i] - 1 == need[i]:             # we just broke a match
            matches -= 1

        o = ord(s2[left]) - ord('a')             # character leaving
        have[o] -= 1
        if have[o] == need[o]:
            matches += 1
        elif have[o] + 1 == need[o]:
            matches -= 1
        left += 1

    return matches == 26

# 1D prefix sum
def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix                 # prefix[r + 1] - prefix[l] == sum of [l, r] inclusive

# Subarray sum equals K — count subarrays with sum == k
def subarray_sum(nums, k):
    from collections import defaultdict
    count = 0
    prefix_count = defaultdict(int)
    prefix_count[0] = 1                # empty prefix
    running = 0
    for x in nums:
        running += x
        count += prefix_count[running - k]
        prefix_count[running] += 1
    return count

# 2D prefix sum — sum of any submatrix in O(1)
def build_2d_prefix(matrix):
    rows, cols = len(matrix), len(matrix[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            prefix[r + 1][c + 1] = (matrix[r][c]
                                    + prefix[r][c + 1]
                                    + prefix[r + 1][c]
                                    - prefix[r][c])
    return prefix

# Sum of submatrix from (r1, c1) to (r2, c2) inclusive
def submatrix_sum(prefix, r1, c1, r2, c2):
    return (prefix[r2 + 1][c2 + 1]
            - prefix[r1][c2 + 1]
            - prefix[r2 + 1][c1]
            + prefix[r1][c1])

def product_except_self(nums):
    n = len(nums)
    result = [1] * n

    prefix = 1
    for i in range(n):                 # result[i] = product of everything LEFT of i
        result[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):     # then multiply in everything RIGHT of i
        result[i] *= suffix
        suffix *= nums[i]

    return result

# Two Sum — key is the complement we still need
def two_sum(nums, target):
    seen = {}                                  # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

# Group Anagrams — key is a canonical form of the word
def group_anagrams(strs):
    from collections import defaultdict
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))               # or a 26-length count tuple: O(n) per word
        groups[key].append(s)
    return list(groups.values())

# Contains Duplicate
def contains_duplicate(nums):
    return len(set(nums)) < len(nums)

# Valid Sudoku — one pass, three dicts of sets. The box key is the insight:
# integer-dividing both coordinates by 3 maps every cell to its 3x3 box.
def is_valid_sudoku(board):
    from collections import defaultdict
    rows, cols, boxes = defaultdict(set), defaultdict(set), defaultdict(set)
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == '.':
                continue
            if v in rows[r] or v in cols[c] or v in boxes[(r // 3, c // 3)]:
                return False
            rows[r].add(v)
            cols[c].add(v)
            boxes[(r // 3, c // 3)].add(v)
    return True

def longest_consecutive(nums):
    seen = set(nums)
    best = 0
    for num in seen:
        if num - 1 in seen:
            continue                           # not the start of a run, skip
        length = 0
        while num + length in seen:
            length += 1
        best = max(best, length)
    return best

def encode(strs):
    return ''.join(f"{len(s)}#{s}" for s in strs)

def decode(s):
    out = []
    i = 0
    while i < len(s):
        j = i
        while s[j] != '#':                   # digits up to the first '#' are the length
            j += 1
        length = int(s[i:j])
        out.append(s[j + 1:j + 1 + length])
        i = j + 1 + length
    return out

# Next Greater Element — for each index, the next larger VALUE to its right (-1 if
# none). Store `i - j` instead, as daily_temperatures does, if you want the distance.
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                          # stores indices, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

# Daily Temperatures — wait days until warmer
def daily_temperatures(temps):
    result = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

# Next Greater Element II — the array is CIRCULAR, so index 0 can be answered by
# something that sits before it. Walk twice and wrap with i % n; pushing only on
# the first lap keeps every index on the stack exactly once.
def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        j = i % n
        while stack and nums[stack[-1]] < nums[j]:
            result[stack.pop()] = nums[j]
        if i < n:
            stack.append(j)
    return result

# Largest Rectangle in Histogram
def largest_rectangle(heights):
    stack = []                          # indices, heights increasing
    best = 0
    for i, h in enumerate(heights + [0]):     # sentinel flushes the stack
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            best = max(best, heights[top] * width)
        stack.append(i)
    return best

# Sliding Window Maximum — monotonic deque
def max_sliding_window(nums, k):
    from collections import deque
    dq = deque()                        # indices, nums[dq] decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:    # drop out-of-window
            dq.popleft()
        while dq and nums[dq[-1]] < x:  # maintain decreasing
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Valid Parentheses
def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

# Evaluate Reverse Polish Notation
def eval_rpn(tokens):
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),   # int() truncates toward zero, a // b floors
    }
    stack = []
    for token in tokens:
        if token in ops:
            right = stack.pop()
            left = stack.pop()           # order matters for - and /
            stack.append(ops[token](left, right))
        else:
            stack.append(int(token))
    return stack.pop()

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []

    def push(self, val):
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)

    def pop(self):
        if self.stack.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.mins[-1]

def basic_calculator(s):
    stack = []
    result = 0
    sign = 1
    i = 0
    while i < len(s):
        c = s[i]
        if c.isdigit():
            num = 0
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            result += sign * num
            continue                      # i already advanced past the number
        if c == '+':
            sign = 1
        elif c == '-':
            sign = -1
        elif c == '(':
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1           # start the sub-expression fresh
        elif c == ')':
            prev_sign = stack.pop()
            prev_result = stack.pop()
            result = prev_result + prev_sign * result
        i += 1
    return result

def car_fleet(target, position, speed):
    stack = []
    for p, s in sorted(zip(position, speed), reverse=True):
        stack.append((target - p) / s)          # time for this car to reach the target
        if len(stack) >= 2 and stack[-1] <= stack[-2]:
            stack.pop()                         # caught the fleet ahead
    return len(stack)

import heapq

# Top K largest — use a MIN-heap of size K (keep the K biggest seen)
def top_k_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)         # evict the smallest in the heap
    return heap                          # K largest (unsorted)

# Top K smallest — use a MAX-heap of size K (negate values)
def top_k_smallest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, -x)
        if len(heap) > k:
            heapq.heappop(heap)
    return [-x for x in heap]

# Built-ins — the same size-k heap internally, O(n log k), result returned sorted.
# Fine to use unless the interviewer wants the heap written out:
#   heapq.nlargest(k, nums)  /  heapq.nsmallest(k, nums)

# K Closest Points to Origin — max-heap of size K by distance
def k_closest(points, k):
    heap = []
    for x, y in points:
        d = -(x*x + y*y)                 # negate for max-heap
        if len(heap) < k:
            heapq.heappush(heap, (d, x, y))
        else:
            heapq.heappushpop(heap, (d, x, y))
    return [[x, y] for _, x, y in heap]

# Merge K Sorted Lists — heap holds the current head of each list
def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # i breaks ties
    dummy = tail = ListNode()
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# Find Median from Data Stream — two heaps, balanced sizes
class MedianFinder:
    def __init__(self):
        self.lo = []      # max-heap (store negated)  — lower half
        self.hi = []      # min-heap                   — upper half

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))   # funnel through lo→hi
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

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

# Task Scheduler — greedy with max-heap of remaining counts
def least_interval(tasks, n):
    from collections import Counter, deque
    counts = Counter(tasks)
    heap = [-c for c in counts.values()]
    heapq.heapify(heap)
    cooldown = deque()                  # (-count, ready_time)
    time = 0
    while heap or cooldown:
        time += 1
        if heap:
            c = heapq.heappop(heap) + 1
            if c < 0:
                cooldown.append((c, time + n))
        if cooldown and cooldown[0][1] == time:
            heapq.heappush(heap, cooldown.popleft()[0])
    return time

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

from collections import Counter
import heapq

def reorganize_string(s):
    n = len(s)
    counts = Counter(s)
    heap = [(-c, ch) for ch, c in counts.items()]       # negate for a max-heap
    heapq.heapify(heap)

    if -heap[0][0] > (n + 1) // 2:
        return ""

    result = [''] * n
    index = 0
    while heap:
        count, ch = heapq.heappop(heap)
        for _ in range(-count):
            result[index] = ch
            index += 2
            if index >= n:
                index = 1                                # wrap to the odd slots
    return ''.join(result)

import heapq

def nth_ugly_number(n):
    heap = [1]
    seen = {1}
    for _ in range(n - 1):
        value = heapq.heappop(heap)
        for prime in (2, 3, 5):
            nxt = value * prime
            if nxt not in seen:
                seen.add(nxt)
                heapq.heappush(heap, nxt)
    return heap[0]

import heapq

def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        first = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if first != second:
            heapq.heappush(heap, -(first - second))
    return -heap[0] if heap else 0

import random

def quickselect(arr, k):                    # kth smallest, 1-indexed; mutates arr
    target = k - 1
    lo, hi = 0, len(arr) - 1
    while True:
        pivot = arr[random.randint(lo, hi)]  # random pivot: sorted input stays O(n)
        # Three-way partition: [lo, lt) < pivot, [lt, gt] == pivot, (gt, hi] > pivot.
        # The == block is what keeps duplicates linear — a two-way split leaves
        # every equal value on one side, so all-equal input goes O(n²).
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if arr[i] < pivot:
                arr[lt], arr[i] = arr[i], arr[lt]
                lt += 1
                i += 1
            elif arr[i] > pivot:
                arr[i], arr[gt] = arr[gt], arr[i]
                gt -= 1                      # i stays: the value swapped in is unseen
            else:
                i += 1
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return pivot                     # target lands inside the == block

# Kth Largest Element — call quickselect with k = len(arr) - k + 1
def find_kth_largest(nums, k):
    return quickselect(nums, len(nums) - k + 1)

from math import inf

# Merge overlapping intervals
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

# Insert interval into sorted, non-overlapping list
def insert_interval(intervals, new):
    result = []
    i, n = 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:
        result.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    result.append(new)
    while i < n:
        result.append(intervals[i]); i += 1
    return result

# Meeting Rooms II — minimum rooms needed
def min_meeting_rooms(intervals):
    import heapq
    intervals.sort(key=lambda x: x[0])
    heap = []                                # end times of ongoing meetings
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)              # reuse a room
        heapq.heappush(heap, end)
    return len(heap)

# Meeting Rooms I — can one person attend everything?
def can_attend_meetings(intervals):
    intervals.sort()
    return all(a[1] <= b[0] for a, b in zip(intervals, intervals[1:]))

# Non-overlapping intervals — minimum removals (greedy by end time)
def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = -inf
    for s, e in intervals:
        if s >= end:
            end = e
        else:
            count += 1
    return count

# Minimum Arrows to Burst Balloons — same greedy, counting kept groups
# instead of removed ones. Sort by end, shoot at the end of the first
# balloon still unburst; that arrow clears everything overlapping it.
def find_min_arrows(points):
    points.sort(key=lambda x: x[1])
    arrows = 0
    limit = -inf
    for start, end in points:
        if start > limit:
            arrows += 1
            limit = end
    return arrows

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    parts = []
    start = end = 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            parts.append(end - start + 1)
            start = i + 1
    return parts

# Minimum rooms via a delta sweep — the counting version of Meeting Rooms II.
# +1 at every start, -1 at every end; the answer is the running maximum.
def min_meeting_rooms_sweep(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    events.sort()                    # ties: -1 sorts before +1, so a room freed
                                     # at time t is reusable at time t
    ongoing = best = 0
    for _, delta in events:
        ongoing += delta
        best = max(best, ongoing)
    return best

from math import inf

def rectangle_area_ii(rectangles):
    xs = sorted({x for r in rectangles for x in (r[0], r[2])})
    total = 0

    for xl, xr in zip(xs, xs[1:]):
        width = xr - xl                          # never 0: xs holds distinct values
        spans = sorted(
            (y1, y2)
            for x1, y1, x2, y2 in rectangles
            if x1 <= xl and x2 >= xr and y1 < y2     # rectangle spans this strip
        )
        covered = 0
        cur_end = -inf
        for y1, y2 in spans:
            y1 = max(y1, cur_end)                  # clip against what's already counted
            if y2 > y1:
                covered += y2 - y1
                cur_end = y2
        total += width * covered

    return total

def count_smaller(nums):
    counts = [0] * len(nums)

    def sort(pairs):
        if len(pairs) <= 1:
            return pairs
        mid = len(pairs) // 2
        left, right = sort(pairs[:mid]), sort(pairs[mid:])

        merged = []
        l = r = 0
        while l < len(left) and r < len(right):
            if left[l][1] <= right[r][1]:
                counts[left[l][0]] += r          # r right-elements already emitted
                merged.append(left[l])
                l += 1
            else:
                merged.append(right[r])
                r += 1
        for i in range(l, len(left)):            # leftovers: all of right was smaller
            counts[left[i][0]] += r
        merged.extend(left[l:])
        merged.extend(right[r:])
        return merged

    sort(list(enumerate(nums)))
    return counts

def get_skyline(buildings):
    if not buildings:
        return []
    return _solve(buildings, 0, len(buildings) - 1)

def _solve(bs, lo, hi):
    if lo == hi:
        left, right, height = bs[lo]
        return [[left, height], [right, 0]]
    mid = (lo + hi) // 2
    return _merge(_solve(bs, lo, mid), _solve(bs, mid + 1, hi))

def _merge(A, B):
    out = []
    i = j = 0
    h1 = h2 = 0                          # current height from each side

    def push(x, h):
        if not out or out[-1][1] != h:   # skip no-op height changes
            out.append([x, h])

    while i < len(A) and j < len(B):
        if A[i][0] < B[j][0]:
            x, h1 = A[i]; i += 1
        elif A[i][0] > B[j][0]:
            x, h2 = B[j]; j += 1
        else:                            # same x: consume both before emitting
            x, h1 = A[i]
            h2 = B[j][1]
            i += 1
            j += 1
        push(x, max(h1, h2))

    for x, h in A[i:]:                   # the exhausted side contributes 0 from here,
        push(x, h)                       # and max(0, h) == h
    for x, h in B[j:]:
        push(x, h)

    return out

# The shape almost every greedy takes
def greedy(items):
    items.sort(key=greedy_key)       # deadline, end time, size, value/weight ratio, ...
    state = initial_state()
    result = 0
    for item in items:
        if is_feasible(item, state):    # take it only if the local choice stays valid
            result += take(item, state)
    return result

from math import inf

# Coin change, greedy version — correct ONLY for canonical coin systems
# (e.g. 1/5/10/25). For arbitrary coins it fails: coins [1, 3, 4], amount 6
# gives 4+1+1 = 3 coins, but the optimum is 3+3 = 2. That case needs DP.
def make_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1

# Jump Game — can you reach the end?
def can_jump(nums):
    farthest = 0
    for i, x in enumerate(nums):
        if i > farthest: return False
        farthest = max(farthest, i + x)
    return True

# Jump Game II — minimum jumps to reach end
def jump(nums):
    jumps = current_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

# Gas Station — find starting index to complete circuit, or -1
def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost): return -1
    tank = start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

# Best Time to Buy/Sell Stock I — single transaction
# Track the minimum price seen so far; best profit is price - min_so_far.
def max_profit(prices):
    min_price = inf
    best = 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best

# Best Time to Buy/Sell Stock II — unlimited transactions
# Sum every positive day-to-day delta (equivalent to capturing every uptrend).
def max_profit_ii(prices):
    return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))

# Activity selection (classic greedy) — see "Non-overlapping intervals" above

# Generic template
def backtrack(state):
    if is_goal(state):
        result.append(state[:])     # copy! state is mutated
        return
    for choice in get_choices(state):
        if is_valid(choice, state):
            make_choice(choice, state)
            backtrack(state)
            undo_choice(choice, state)

# Permutations
def permutations(nums):
    result = []
    def bt(current, used):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i, x in enumerate(nums):
            if used[i]: continue
            used[i] = True
            current.append(x)
            bt(current, used)
            current.pop()
            used[i] = False
    bt([], [False] * len(nums))
    return result

# Subsets (power set)
def subsets(nums):
    result = []
    def bt(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            bt(i + 1, current)
            current.pop()
    bt(0, [])
    return result

# Combinations — choose k from n
def combine(n, k):
    result = []
    def bt(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, n + 1):
            current.append(i)
            bt(i + 1, current)
            current.pop()
    bt(1, [])
    return result

# Combination Sum (with repetition allowed)
def combination_sum(candidates, target):
    result = []
    candidates.sort()
    def bt(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break
            current.append(candidates[i])
            bt(i, current, remaining - candidates[i])    # i, not i+1 — reuse allowed
            current.pop()
    bt(0, [], target)
    return result

# Word Search in grid
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word): return True
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or board[r][c] != word[i]):
            return False
        board[r][c] = '#'                    # mark visited
        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1)
                 or dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        board[r][c] = word[i]                # restore
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

# N-Queens — use three sets for O(1) attack checks
def solve_n_queens(n):
    result = []
    cols, diag1, diag2 = set(), set(), set()   # diag1: r-c, diag2: r+c
    queens = []

    def bt(row):
        if row == n:
            board = ['.' * c + 'Q' + '.' * (n - c - 1) for c in queens]
            result.append(board)
            return
        for c in range(n):
            if c in cols or (row - c) in diag1 or (row + c) in diag2:
                continue
            cols.add(c); diag1.add(row - c); diag2.add(row + c)
            queens.append(c)
            bt(row + 1)
            queens.pop()
            cols.discard(c); diag1.discard(row - c); diag2.discard(row + c)

    bt(0)
    return result

# Generate Parentheses — prune by counts instead of validating at the leaf.
# Open a bracket while any remain; close one only while it would stay balanced.
def generate_parentheses(n):
    result = []
    current = []
    def bt(opened, closed):
        if len(current) == 2 * n:
            result.append(''.join(current))
            return
        if opened < n:
            current.append('(')
            bt(opened + 1, closed)
            current.pop()
        if opened > closed:
            current.append(')')
            bt(opened, closed + 1)
            current.pop()
    bt(0, 0)
    return result

# Palindrome Partitioning — the choice at each step is where to cut next
def partition(s):
    result = []

    def is_palindrome(i, j):
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    def bt(start, current):
        if start >= len(s):
            result.append(current[:])
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):        # prune: only cut on a palindrome
                current.append(s[start:end + 1])
                bt(end + 1, current)
                current.pop()

    bt(0, [])
    return result

# Subsets II / Combination Sum II shape
def subsets_with_dup(nums):
    nums.sort()
    result = []
    def bt(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                         # same value, same level → same subtree
            current.append(nums[i])
            bt(i + 1, current)
            current.pop()
    bt(0, [])
    return result

from functools import cache

# Decode Ways — count decodings of a digit string ('1'..'26' → 'A'..'Z')
def decode_ways(digits):
    @cache
    def dfs(i):
        if i == len(digits):
            return 1                           # consumed everything: one valid decoding
        if digits[i] == '0':
            return 0                           # no letter starts with 0
        ways = dfs(i + 1)
        if 10 <= int(digits[i:i + 2]) <= 26:      # slicing past the end is safe
            ways += dfs(i + 2)
        return ways
    return dfs(0)

from functools import cache

@cache                      # Python 3.9+; lru_cache(maxsize=None) is the older spelling
def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

# AVOID the mutable-default-argument anti-pattern:
#   def fib(n, memo={}):  ← cache leaks across calls!

# Arguments must be hashable — pass indices, not lists.
# For grid states use two ints; for a set of chosen items use a bitmask or frozenset.

def solve(nums):
    @cache
    def dfs(i):
        ...
    return dfs(0)

def fib_tab(n):
    if n < 2: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

# Climbing Stairs — 1 or 2 steps at a time. Fibonacci in disguise.
def climb_stairs(n):
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

# Tribonacci — same shape, window of 3
def tribonacci(n):
    if n < 3:
        return 0 if n == 0 else 1
    a, b, c = 0, 1, 1
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c
    return c

# Min Cost Climbing Stairs — pay when you LEAVE a step
def min_cost_climbing_stairs(cost):
    prev2 = prev1 = 0
    for i in range(2, len(cost) + 1):
        prev2, prev1 = prev1, min(prev1 + cost[i - 1], prev2 + cost[i - 2])
    return prev1

def rob(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

# House Robber II — houses in a circle, so the first and last are adjacent.
# Run the linear version twice: once excluding the last house, once excluding the first.
def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]
    return max(rob(nums[:-1]), rob(nums[1:]))

from functools import cache

def mincost_tickets(days, costs):
    travel = set(days)
    last = days[-1]

    @cache
    def dfs(day):
        if day > last:
            return 0
        if day not in travel:
            return dfs(day + 1)              # free: skip to the next day
        return min(
            costs[0] + dfs(day + 1),
            costs[1] + dfs(day + 7),
            costs[2] + dfs(day + 30),
        )

    return dfs(days[0])

from functools import cache

# Partition Array for Maximum Sum — every subarray of length <= k is replaced
# by its maximum, and we maximise the total.
def partition_array_for_maximum_sum(arr, k):
    n = len(arr)

    @cache
    def dfs(i):
        if i == n:
            return 0
        best = 0
        block_max = 0
        for j in range(i, min(i + k, n)):        # block is arr[i..j]
            block_max = max(block_max, arr[j])
            length = j - i + 1
            best = max(best, block_max * length + dfs(j + 1))
        return best

    return dfs(0)

from functools import cache
from math import inf

# Unique Paths — count routes from top-left to bottom-right moving right/down
def unique_paths(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            dp[c] += dp[c - 1]               # dp[c] is the row above, dp[c-1] the left
    return dp[n - 1]

# With obstacles — a blocked cell contributes zero routes
def unique_paths_with_obstacles(grid):
    n = len(grid[0])
    dp = [0] * n
    dp[0] = 1
    for row in grid:
        for c in range(n):
            if row[c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[-1]

# Minimum Path Sum
def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])

    @cache
    def dfs(r, c):
        if r == rows - 1 and c == cols - 1:
            return grid[r][c]
        if r >= rows or c >= cols:
            return inf
        return grid[r][c] + min(dfs(r + 1, c), dfs(r, c + 1))

    return dfs(0, 0)

# Triangle — minimum top-to-bottom path; row r+1 has one more entry than row r
def minimum_total(triangle):
    @cache
    def dfs(r, c):
        if r == len(triangle):
            return 0
        return triangle[r][c] + min(dfs(r + 1, c), dfs(r + 1, c + 1))
    return dfs(0, 0)

# Maximal Square — dp[r][c] = side of the largest all-ones square ENDING at (r, c).
# It is limited by the worst of its three neighbours, hence min(...) + 1.
# Cells are ints here; LeetCode passes '0'/'1' strings, so test == '0' there.
def maximal_square(matrix):
    @cache
    def dfs(r, c):
        if r < 0 or c < 0 or matrix[r][c] == 0:
            return 0
        return 1 + min(dfs(r - 1, c), dfs(r, c - 1), dfs(r - 1, c - 1))

    best = 0
    for r in range(len(matrix)):
        for c in range(len(matrix[0])):
            best = max(best, dfs(r, c))
    return best * best

from functools import cache
from math import inf

def calculate_minimum_hp(dungeon):
    last_row, last_col = len(dungeon) - 1, len(dungeon[0]) - 1

    @cache
    def dfs(r, c):
        if r > last_row or c > last_col:
            return inf
        if r == last_row and c == last_col:
            return max(1, 1 - dungeon[r][c])
        return max(1, min(dfs(r + 1, c), dfs(r, c + 1)) - dungeon[r][c])

    return dfs(0, 0)

from math import inf

def coin_change(coins, amount):
    dp = [inf] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != inf else -1

def length_of_LIS(nums):
    import bisect
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

from functools import cache

def lcs(text1, text2):
    @cache
    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0                         # one string is used up
        if text1[i] == text2[j]:
            return 1 + dfs(i + 1, j + 1)
        return max(dfs(i + 1, j), dfs(i, j + 1))
    return dfs(0, 0)

from functools import cache

def min_distance(word1, word2):
    @cache
    def dfs(i, j):
        if i == len(word1):
            return len(word2) - j            # insert whatever word2 has left
        if j == len(word2):
            return len(word1) - i            # delete whatever word1 has left
        if word1[i] == word2[j]:
            return dfs(i + 1, j + 1)
        return 1 + min(dfs(i + 1, j),        # delete word1[i]
                       dfs(i, j + 1),        # insert word2[j]
                       dfs(i + 1, j + 1))    # replace word1[i] with word2[j]
    return dfs(0, 0)

from functools import cache

def num_distinct(s, t):
    @cache
    def dfs(i, j):
        if j == len(t):
            return 1                     # matched all of t: one full subsequence
        if i == len(s):
            return 0                     # ran out of s with t unfinished
        count = dfs(i + 1, j)            # skip s[i]
        if s[i] == t[j]:
            count += dfs(i + 1, j + 1)   # or use it
        return count
    return dfs(0, 0)

from functools import cache

def minimum_delete_sum(s1, s2):
    @cache
    def dfs(i, j):
        if i == len(s1):
            return sum(map(ord, s2[j:]))
        if j == len(s2):
            return sum(map(ord, s1[i:]))
        if s1[i] == s2[j]:
            return dfs(i + 1, j + 1)
        return min(ord(s1[i]) + dfs(i + 1, j), ord(s2[j]) + dfs(i, j + 1))
    return dfs(0, 0)

from functools import cache

def shortest_common_supersequence(str1, str2):
    @cache
    def dfs(i, j):
        if i == len(str1):
            return str2[j:]
        if j == len(str2):
            return str1[i:]
        if str1[i] == str2[j]:
            return str1[i] + dfs(i + 1, j + 1)      # one copy covers both
        take1 = str1[i] + dfs(i + 1, j)
        take2 = str2[j] + dfs(i, j + 1)
        return take1 if len(take1) <= len(take2) else take2
    return dfs(0, 0)

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    # looping over coins on the OUTSIDE counts combinations, not permutations
    for c in coins:
        for i in range(c, amount + 1):
            dp[i] += dp[i - c]
    return dp[amount]

# 0/1 — each item once. Iterate capacity DOWNWARD so dp[j - w] is still
# the previous row (this item not yet used).
def knapsack_01(items, capacity):            # items: (weight, value)
    dp = [0] * (capacity + 1)
    for w, v in items:
        for j in range(capacity, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

# Unbounded — unlimited copies. Iterate capacity UPWARD so dp[j - w] may
# already include this item.
def knapsack_unbounded(items, capacity):
    dp = [0] * (capacity + 1)
    for w, v in items:
        for j in range(w, capacity + 1):     # the ONLY difference is this range
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

# Partition Equal Subset Sum — reachability instead of value
def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    reachable = {0}
    for x in nums:
        reachable |= {r + x for r in reachable if r + x <= target}
    return target in reachable

# Target Sum — assign + or - to every number so the result is `target`.
# State is (index, running total); the two branches are the two signs.
from functools import cache
from math import inf

def find_target_sum_ways(nums, target):
    @cache
    def dfs(i, total):
        if i == len(nums):
            return 1 if total == target else 0
        return dfs(i + 1, total + nums[i]) + dfs(i + 1, total - nums[i])
    return dfs(0, 0)

# Choosing signs is equivalent to choosing the subset P that gets a plus:
#   sum(P) - (total - sum(P)) = target  ->  sum(P) = (total + target) / 2
# so the same problem can be counted as a 0/1 subset-sum, which is what makes
# the bounded-capacity table below applicable.
def find_target_sum_ways_knapsack(nums, target):
    total = sum(nums)
    if (total + target) % 2 or abs(target) > total:
        return 0
    capacity = (total + target) // 2

    dp = [0] * (capacity + 1)
    dp[0] = 1
    for x in nums:
        for j in range(capacity, x - 1, -1):      # 0/1 -> downward
            dp[j] += dp[j - x]
    return dp[capacity]

# Perfect Squares — unbounded knapsack where the "coins" are 1, 4, 9, 16, ...
def num_squares(n):
    dp = [inf] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        k = 1
        while k * k <= i:
            dp[i] = min(dp[i], dp[i - k * k] + 1)
            k += 1
    return dp[n]

def bounded_knapsack(items, capacity):      # items: (weight, value, quantity)
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value, quantity = items[i - 1]
        for j in range(capacity + 1):
            best = dp[i - 1][j]                       # take 0 copies
            for count in range(1, quantity + 1):
                total_weight = count * weight
                if total_weight > j:
                    break
                best = max(best, dp[i - 1][j - total_weight] + count * value)
            dp[i][j] = best
    return dp[n][capacity]

def bounded_knapsack_binary(items, capacity):
    expanded = []
    for weight, value, quantity in items:
        chunk = 1
        while chunk <= quantity:
            expanded.append((chunk * weight, chunk * value))
            quantity -= chunk
            chunk *= 2
        if quantity > 0:
            expanded.append((quantity * weight, quantity * value))

    dp = [0] * (capacity + 1)
    for w, v in expanded:
        for j in range(capacity, w - 1, -1):          # 0/1 → downward
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)             # dp[i] = can s[:i] be segmented?
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1                   # single chars are palindromes of length 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = (dp[i + 1][j - 1] if length > 2 else 0) + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

def longest_palindrome(s):
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]        # last valid window

    best = ""
    for i in range(len(s)):
        for p in (expand(i, i), expand(i, i + 1)):   # odd and even centers
            if len(p) > len(best):
                best = p
    return best

def min_cut(s):
    n = len(s)
    # Precompute: is_pal[i][j] = True iff s[i:j+1] is a palindrome
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True

    cuts = [0] * n
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            cuts[i] = min(cuts[j] + 1 for j in range(i) if is_pal[j + 1][i])
    return cuts[n - 1]

from functools import cache

# Count Palindromic Substrings — shrink from both ends
def count_palindromic_substrings(s):
    @cache
    def is_pal(i, j):
        if i >= j:
            return True
        return s[i] == s[j] and is_pal(i + 1, j - 1)
    return sum(is_pal(i, j) for i in range(len(s)) for j in range(i, len(s)))

# Burst Balloons — split at k, the LAST balloon burst inside the range. By then
# its neighbours are the untouched balloons just outside, which is exactly what
# makes the two halves independent. Pad with 1s so the edges need no special case.
def burst_balloons(nums):
    balloons = [1] + nums + [1]

    @cache
    def dfs(i, j):                       # inclusive range of `balloons` indices
        if i > j:
            return 0
        return max(balloons[i - 1] * balloons[k] * balloons[j + 1]
                   + dfs(i, k - 1) + dfs(k + 1, j)
                   for k in range(i, j + 1))

    return dfs(1, len(balloons) - 2)