def full_justify(words, maxWidth):
    result = []
    line = []
    line_len = 0
    for word in words:
        if line_len + len(word) + len(line) > maxWidth:
            spaces = maxWidth - line_len
            slots = max(len(line) - 1, 1)
            for i in range(spaces):
                line[i % slots] += ' '
            result.append(''.join(line))
            line = []
            line_len = 0
        line.append(word)
        line_len += len(word)
    # Last line: left-justified
    result.append(' '.join(line).ljust(maxWidth))
    return result

import random

class SkipNode:
    def __init__(self, val, level):
        self.val = val
        self.next = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=16):
        self.max_level = max_level
        self.head = SkipNode(float('-inf'), max_level)
        self.level = 0

    def _random_level(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.max_level:
            lvl += 1
        return lvl

    def search(self, target):
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.next[i] and curr.next[i].val < target:
                curr = curr.next[i]
        curr = curr.next[0]
        return curr and curr.val == target

    def insert(self, val):
        update = [self.head] * (self.max_level + 1)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.next[i] and curr.next[i].val < val:
                curr = curr.next[i]
            update[i] = curr
        lvl = self._random_level()
        self.level = max(self.level, lvl)
        node = SkipNode(val, lvl)
        for i in range(lvl + 1):
            node.next[i] = update[i].next[i]
            update[i].next[i] = node

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    base, mod = 256, 101
    p_hash = t_hash = 0
    h = pow(base, m - 1, mod)
    matches = []
    for i in range(m):
        p_hash = (base * p_hash + ord(pattern[i])) % mod
        t_hash = (base * t_hash + ord(text[i])) % mod
    for i in range(n - m + 1):
        if p_hash == t_hash:
            if text[i:i+m] == pattern:
                matches.append(i)
        if i < n - m:
            t_hash = (base * (t_hash - ord(text[i]) * h)
                      + ord(text[i + m])) % mod
            t_hash = (t_hash + mod) % mod
    return matches

def unique_paths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[n - 1]

# unique_paths(3, 7) → 28

from math import comb
def unique_paths_math(m, n):
    return comb(m + n - 2, m - 1)

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negated)
        self.hi = []  # min-heap

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        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

import random

def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir

# Each element has k/n probability of being selected

def compress(chars):
    write = read = 0
    while read < len(chars):
        ch = chars[read]
        count = 0
        while read < len(chars) and chars[read] == ch:
            read += 1
            count += 1
        chars[write] = ch
        write += 1
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1
    return write

# ['a','a','b','b','c','c','c'] → ['a','2','b','2','c','3']

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        i += 1  # 1-indexed
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def range_query(self, l, r):
        return self.query(r) - (self.query(l-1) if l > 0 else 0)

import heapq

def smallest_range(lists):
    heap = []
    curr_max = float('-inf')
    for i, lst in enumerate(lists):
        heapq.heappush(heap, (lst[0], i, 0))
        curr_max = max(curr_max, lst[0])
    best = [float('-inf'), float('inf')]
    while True:
        curr_min, li, idx = heapq.heappop(heap)
        if curr_max - curr_min < best[1] - best[0]:
            best = [curr_min, curr_max]
        if idx + 1 == len(lists[li]):
            break
        nxt = lists[li][idx + 1]
        curr_max = max(curr_max, nxt)
        heapq.heappush(heap, (nxt, li, idx + 1))
    return best

import heapq
from collections import Counter

def reorganize_string(s):
    count = Counter(s)
    heap = [(-freq, ch) for ch, freq in count.items()]
    heapq.heapify(heap)
    result = []
    prev_freq, prev_ch = 0, ''
    while heap:
        freq, ch = heapq.heappop(heap)
        result.append(ch)
        if prev_freq < 0:
            heapq.heappush(heap, (prev_freq, prev_ch))
        prev_freq, prev_ch = freq + 1, ch
    result = ''.join(result)
    return result if len(result) == len(s) else ""

# reorganize_string("aab") → "aba"

def car_fleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    fleets = 0
    prev_time = 0
    for pos, spd in cars:
        time = (target - pos) / spd
        if time > prev_time:
            fleets += 1
            prev_time = time
    return fleets

# car_fleet(12, [10,8,0,5,3], [2,4,1,1,3]) → 3

def find_min_rotated(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

# With duplicates
def find_min_rotated_dup(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            hi = mid
        else:
            hi -= 1  # can't decide, shrink
    return nums[lo]

# find_min_rotated([3,4,5,1,2]) → 1
# find_min_rotated_dup([2,2,2,0,1]) → 0

def min_cost(n, cuts):
    cuts = sorted([0] + cuts + [n])
    m = len(cuts)
    dp = [[0]*m for _ in range(m)]
    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i+1, j):
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k][j] + cuts[j] - cuts[i])
    return dp[0][m-1]

def count_distinct_substrings(s):
    n = len(s)
    sa = build_suffix_array(s)   # from Suffix Array card
    lcp = build_lcp(s, sa)       # from Suffix Array card
    total = n * (n + 1) // 2
    return total - sum(lcp)

# "abab" → total=10, lcp=[0,2,0,1], distinct=10-3=7
# Substrings: a, ab, aba, abab, b, ba, bab

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def chinese_remainder(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
    result = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        _, inv, _ = extended_gcd(Mi, m)
        result += r * Mi * inv
    return result % M

# x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
# chinese_remainder([2, 3, 5], [3, 5, 7]) → 68
# Verify: 68%3=2, 68%5=3, 68%7=5 ✓

from bisect import bisect_left, insort

def max_sum_submatrix(matrix, k):
    m, n = len(matrix), len(matrix[0])
    result = float('-inf')
    for left in range(n):
        row_sum = [0] * m
        for right in range(left, n):
            for r in range(m):
                row_sum[r] += matrix[r][right]
            # Find max subarray sum <= k
            sorted_sums = [0]
            prefix = 0
            for s in row_sum:
                prefix += s
                idx = bisect_left(sorted_sums, prefix - k)
                if idx < len(sorted_sums):
                    result = max(result, prefix - sorted_sums[idx])
                insort(sorted_sums, prefix)
    return result

from collections import deque

def bfs_01(graph, src, n):
    dist = [float('inf')] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:  # w is 0 or 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

def int_to_roman(num):
    vals = [(1000,'M'),(900,'CM'),(500,'D'),(400,'CD'),
            (100,'C'),(90,'XC'),(50,'L'),(40,'XL'),
            (10,'X'),(9,'IX'),(5,'V'),(4,'IV'),(1,'I')]
    result = []
    for v, s in vals:
        while num >= v:
            result.append(s)
            num -= v
    return ''.join(result)

def roman_to_int(s):
    vals = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
    result = 0
    for i in range(len(s)):
        if i + 1 < len(s) and vals[s[i]] < vals[s[i+1]]:
            result -= vals[s[i]]
        else:
            result += vals[s[i]]
    return result

import hashlib

class BloomFilter:
    def __init__(self, size=1000, num_hashes=3):
        self.size = size
        self.num_hashes = num_hashes
        self.bits = [False] * size

    def _hashes(self, item):
        for i in range(self.num_hashes):
            h = hashlib.md5(f"{item}{i}".encode()).hexdigest()
            yield int(h, 16) % self.size

    def add(self, item):
        for idx in self._hashes(item):
            self.bits[idx] = True

    def might_contain(self, item):
        return all(self.bits[idx] for idx in self._hashes(item))

# bf = BloomFilter(10000, 5)
# bf.add("hello")
# bf.might_contain("hello") → True
# bf.might_contain("world") → probably False

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key):
        return key % self.size

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        for k, v in self.buckets[self._hash(key)]:
            if k == key:
                return v
        return -1

    def remove(self, key):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                return

def interval_intersection(A, B):
    i = j = 0
    result = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            result.append([lo, hi])
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

def count_primes(n):
    if n < 3:
        return 0
    is_prime = bytearray(b'\x01') * n
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
    return sum(is_prime)

# Segmented sieve for large ranges
def segmented_sieve(lo, hi):
    import math
    limit = int(math.sqrt(hi)) + 1
    primes = []
    sieve = [True] * (limit + 1)
    for i in range(2, limit + 1):
        if sieve[i]:
            primes.append(i)
            for j in range(i*i, limit+1, i):
                sieve[j] = False
    is_prime = [True] * (hi - lo + 1)
    for p in primes:
        start = max(p*p, ((lo + p - 1) // p) * p)
        for j in range(start, hi+1, p):
            is_prime[j - lo] = False
    if lo <= 1:
        is_prime[1 - lo] = False
    return [i + lo for i in range(hi - lo + 1) if is_prime[i]]

# count_primes(100) → 25

# Using sortedcontainers (pip install sortedcontainers)
from sortedcontainers import SortedList

sl = SortedList([5, 1, 3])
sl.add(2)          # [1, 2, 3, 5]
sl.remove(3)       # [1, 2, 5]
sl.bisect_left(2)  # 1 (index of 2)
sl[0]              # 1 (min)
sl[-1]             # 5 (max)

# BIT-backed order statistic (values in [0, MAXVAL])
class OrderStatistic:
    def __init__(self, maxval):
        self.n = maxval + 1
        self.bit = [0] * (self.n + 1)

    def update(self, i, delta):
        i += 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)

    def query(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & (-i)
        return s

    def kth(self, k):
        pos = 0
        bitlen = self.n.bit_length()
        for i in range(bitlen, -1, -1):
            npos = pos + (1 << i)
            if npos <= self.n and self.bit[npos] < k:
                k -= self.bit[npos]
                pos = npos
        return pos

def multi_pattern_search(text, patterns):
    if not patterns:
        return {}
    base, mod = 31, 10**9 + 9
    results = {p: [] for p in patterns}
    by_len = {}
    for p in patterns:
        by_len.setdefault(len(p), []).append(p)

    def compute_hash(s):
        h = 0
        for c in s:
            h = (h * base + ord(c)) % mod
        return h

    for plen, pats in by_len.items():
        pat_hashes = {}
        for p in pats:
            h = compute_hash(p)
            pat_hashes.setdefault(h, []).append(p)
        # Rolling hash over text
        h = compute_hash(text[:plen])
        power = pow(base, plen - 1, mod)
        for i in range(len(text) - plen + 1):
            if i > 0:
                h = (h - ord(text[i-1]) * power) % mod
                h = (h * base + ord(text[i+plen-1])) % mod
            if h in pat_hashes:
                for p in pat_hashes[h]:
                    if text[i:i+plen] == p:
                        results[p].append(i)
    return results

# multi_pattern_search("abcabcabc", ["abc","cab"])
# → {"abc": [0,3,6], "cab": [2,5]}

def max_coins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):  # gap between l and r
        for l in range(0, n - length):
            r = l + length
            for k in range(l + 1, r):  # last to burst
                dp[l][r] = max(dp[l][r],
                    dp[l][k] + dp[k][r] +
                    nums[l] * nums[k] * nums[r])
    return dp[0][n - 1]

# max_coins([3,1,5,8]) → 167

def int_to_roman(num):
    vals = [(1000,'M'),(900,'CM'),(500,'D'),(400,'CD'),
            (100,'C'),(90,'XC'),(50,'L'),(40,'XL'),
            (10,'X'),(9,'IX'),(5,'V'),(4,'IV'),(1,'I')]
    result = []
    for v, s in vals:
        while num >= v:
            result.append(s)
            num -= v
    return ''.join(result)

def roman_to_int(s):
    vals = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
    result = 0
    for i in range(len(s)):
        if i + 1 < len(s) and vals[s[i]] < vals[s[i+1]]:
            result -= vals[s[i]]
        else:
            result += vals[s[i]]
    return result

def spf_sieve(N):
    spf = list(range(N + 1))
    for i in range(2, int(N**0.5) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i*i, N + 1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

def factorize(n, spf):
    factors = {}
    while n > 1:
        p = spf[n]
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    return factors

# spf = spf_sieve(100)
# factorize(60, spf) → {2: 2, 3: 1, 5: 1}
# factorize(84, spf) → {2: 2, 3: 1, 7: 1}

def longest_valid_parentheses(s):
    stack = [-1]
    max_len = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

# longest_valid_parentheses(")()())") → 4
# longest_valid_parentheses("()(()") → 2

def reorder_list(head):
    if not head or not head.next:
        return
    # 1. Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # 2. Reverse second half
    prev = None
    curr = slow.next
    slow.next = None
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    # 3. Merge alternately
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

# 1→2→3→4→5 becomes 1→5→2→4→3

def bidirectional_bfs(begin, end, word_list):
    word_set = set(word_list)
    if end not in word_set: return 0
    front = {begin}
    back = {end}
    visited = {begin, end}
    steps = 1
    while front and back:
        if len(front) > len(back):
            front, back = back, front
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    nw = word[:i] + c + word[i+1:]
                    if nw in back:
                        return steps + 1
                    if nw in word_set and nw not in visited:
                        visited.add(nw)
                        next_front.add(nw)
        front = next_front
        steps += 1
    return 0

from collections import deque, defaultdict

def alien_order(words):
    adj = defaultdict(set)
    in_deg = {c: 0 for w in words for c in w}
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i+1]
        if len(w1) > len(w2) and w1[:len(w2)] == w2:
            return ""  # invalid: prefix comes after
        for a, b in zip(w1, w2):
            if a != b:
                if b not in adj[a]:
                    adj[a].add(b)
                    in_deg[b] += 1
                break
    queue = deque(c for c in in_deg if in_deg[c] == 0)
    result = []
    while queue:
        c = queue.popleft()
        result.append(c)
        for nb in adj[c]:
            in_deg[nb] -= 1
            if in_deg[nb] == 0:
                queue.append(nb)
    return ''.join(result) if len(result) == len(in_deg) else ""

# alien_order(["wrt","wrf","er","ett","rftt"]) → "wertf"

import bisect
import hashlib

class ConsistentHash:
    def __init__(self, replicas=150):
        self.replicas = replicas
        self.ring = []       # sorted hash positions
        self.node_map = {}   # hash → node name

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            bisect.insort(self.ring, h)
            self.node_map[h] = node

    def remove_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            self.ring.remove(h)
            del self.node_map[h]

    def get_node(self, key):
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h) % len(self.ring)
        return self.node_map[self.ring[idx]]

# ch = ConsistentHash(replicas=3)
# ch.add_node("server1")
# ch.add_node("server2")
# ch.get_node("my_key") → "server1" or "server2"

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or board[r][c] != word[idx]):
            return False
        temp = board[r][c]
        board[r][c] = '#'
        found = any(dfs(r+dr, c+dc, idx+1)
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)])
        board[r][c] = temp
        return found
    return any(dfs(r, c, 0)
        for r in range(rows) for c in range(cols))

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s == 0:
                result.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                lo += 1; hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return result

def longest_common_prefix(strs):
    if not strs:
        return ""
    for i in range(len(strs[0])):
        ch = strs[0][i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != ch:
                return strs[0][:i]
    return strs[0]

# longest_common_prefix(["flower","flow","flight"]) → "fl"

def counting_sort_neg(arr):
    if not arr:
        return arr
    min_val = min(arr)
    max_val = max(arr)
    k = max_val - min_val + 1
    count = [0] * k
    for x in arr:
        count[x - min_val] += 1
    result = []
    for i in range(k):
        result.extend([i + min_val] * count[i])
    return result

# counting_sort_neg([-5, -3, 0, 2, -1, 4, -3])
# → [-5, -3, -3, -1, 0, 2, 4]

def bucket_sort(arr, num_buckets=10):
    if not arr:
        return arr
    min_val, max_val = min(arr), max(arr)
    bucket_range = (max_val - min_val) / num_buckets + 1
    buckets = [[] for _ in range(num_buckets)]
    for x in arr:
        idx = int((x - min_val) / bucket_range)
        buckets[idx].append(x)
    result = []
    for bucket in buckets:
        result.extend(sorted(bucket))
    return result

# bucket_sort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47])

def min_platforms(arrivals, departures):
    events = []
    for a in arrivals:
        events.append((a, 1))
    for d in departures:
        events.append((d + 0.5, -1))  # depart after arrive at same time
    events.sort()
    curr = max_platforms = 0
    for _, delta in events:
        curr += delta
        max_platforms = max(max_platforms, curr)
    return max_platforms

# min_platforms([900,940,950,1100],[910,1200,1120,1130]) → 3

from collections import deque

def max_flow(graph, source, sink, n):
    # graph[u][v] = capacity
    def bfs(source, sink, parent):
        visited = {source}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in range(n):
                if v not in visited and graph[u][v] > 0:
                    visited.add(v)
                    parent[v] = u
                    if v == sink:
                        return True
                    queue.append(v)
        return False

    total_flow = 0
    parent = [-1] * n
    while bfs(source, sink, parent):
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, graph[u][v])
            v = u
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = u
        total_flow += path_flow
        parent = [-1] * n
    return total_flow

def find_bridges(graph, n):
    disc = [-1] * n
    low = [-1] * n
    parent = [-1] * n
    bridges = []
    timer = [0]

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph[u]:
            if disc[v] == -1:
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return bridges

# Using sortedcontainers (pip install sortedcontainers)
from sortedcontainers import SortedList

sl = SortedList([5, 1, 3])
sl.add(2)          # [1, 2, 3, 5]
sl.remove(3)       # [1, 2, 5]
sl.bisect_left(2)  # 1 (index of 2)
sl[0]              # 1 (min)
sl[-1]             # 5 (max)

# BIT-backed order statistic (values in [0, MAXVAL])
class OrderStatistic:
    def __init__(self, maxval):
        self.n = maxval + 1
        self.bit = [0] * (self.n + 1)

    def update(self, i, delta):
        i += 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)

    def query(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & (-i)
        return s

    def kth(self, k):
        pos = 0
        bitlen = self.n.bit_length()
        for i in range(bitlen, -1, -1):
            npos = pos + (1 << i)
            if npos <= self.n and self.bit[npos] < k:
                k -= self.bit[npos]
                pos = npos
        return pos

def max_coins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):  # gap between l and r
        for l in range(0, n - length):
            r = l + length
            for k in range(l + 1, r):  # last to burst
                dp[l][r] = max(dp[l][r],
                    dp[l][k] + dp[k][r] +
                    nums[l] * nums[k] * nums[r])
    return dp[0][n - 1]

# max_coins([3,1,5,8]) → 167

def max_bipartite_matching(graph, n_left, n_right):
    # graph[u] = list of right nodes u can match to
    match_right = [-1] * n_right

    def dfs(u, visited):
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                if match_right[v] == -1 or dfs(match_right[v], visited):
                    match_right[v] = u
                    return True
        return False

    result = 0
    for u in range(n_left):
        visited = [False] * n_right
        if dfs(u, visited):
            result += 1
    return result

# graph = {0:[0,1], 1:[0], 2:[1,2]}
# max_bipartite_matching(graph, 3, 3) → 3

def trap_stack(height):
    stack = []  # indices
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = height[stack.pop()]
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded = min(h, height[stack[-1]]) - bottom
            water += width * bounded
        stack.append(i)
    return water

# trap_stack([0,1,0,2,1,0,1,3,2,1,2,1]) → 6

def maximal_rectangle(matrix):
    if not matrix: return 0
    n = len(matrix[0])
    heights = [0] * (n + 1)
    max_area = 0
    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        # Largest rectangle in histogram
        stack = []
        for i in range(n + 1):
            while stack and heights[stack[-1]] > heights[i]:
                h = heights[stack.pop()]
                w = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(i)
    return max_area

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, inv_l = count_inversions(arr[:mid])
    right, inv_r = count_inversions(arr[mid:])
    merged = []
    inversions = inv_l + inv_r
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inversions += len(left) - i
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

# _, inv = count_inversions([2, 4, 1, 3, 5])
# inv → 3 (pairs: (2,1), (4,1), (4,3))

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x):
        self.stack_in.append(x)

    def pop(self):
        self._move()
        return self.stack_out.pop()

    def peek(self):
        self._move()
        return self.stack_out[-1]

    def empty(self):
        return not self.stack_in and not self.stack_out

    def _move(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())

class BIT_RangeUpdate:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def _update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def range_add(self, l, r, val):
        self._update(l, val)
        if r + 1 <= self.n:
            self._update(r + 1, -val)

    def point_query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

# bit = BIT_RangeUpdate(5)
# bit.range_add(2, 4, 3)  # add 3 to positions 2..4
# [bit.point_query(i) for i in range(1, 6)]
# → [0, 3, 3, 3, 0]

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)   # userId → [(time, tweetId)]
        self.follows = defaultdict(set)   # userId → {followeeIds}

    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.time, tweetId))
        self.time -= 1  # negative for max-heap via min-heap

    def getNewsFeed(self, userId):
        heap = []
        self.follows[userId].add(userId)
        for uid in self.follows[userId]:
            if self.tweets[uid]:
                idx = len(self.tweets[uid]) - 1
                t, tid = self.tweets[uid][idx]
                heapq.heappush(heap, (t, tid, uid, idx))
        feed = []
        while heap and len(feed) < 10:
            t, tid, uid, idx = heapq.heappop(heap)
            feed.append(tid)
            if idx > 0:
                t2, tid2 = self.tweets[uid][idx-1]
                heapq.heappush(heap, (t2, tid2, uid, idx-1))
        return feed

    def follow(self, followerId, followeeId):
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        self.follows[followerId].discard(followeeId)

def min_arborescence(n, edges, root):
    # edges = [(u, v, w), ...]
    INF = float('inf')
    res = 0
    while True:
        # Find min incoming edge for each node
        min_in = [INF] * n
        best_from = [-1] * n
        for u, v, w in edges:
            if u != v and v != root and w < min_in[v]:
                min_in[v] = w
                best_from[v] = u
        for i in range(n):
            if i != root and min_in[i] == INF:
                return INF  # unreachable
        # Detect cycles in chosen edges
        comp = [-1] * n
        comp[root] = root
        num_comp = 0
        visited = [-1] * n
        for i in range(n):
            if i == root:
                continue
            res += min_in[i]
            u = i
            while visited[u] == -1 and comp[u] == -1:
                visited[u] = i
                u = best_from[u]
            if comp[u] == -1 and u != root:
                # Found cycle, label it
                v = u
                while True:
                    comp[v] = num_comp
                    v = best_from[v]
                    if v == u: break
                num_comp += 1
        if num_comp == 0:
            break
        for i in range(n):
            if comp[i] == -1:
                comp[i] = num_comp
                num_comp += 1
        # Contract and adjust edges
        new_edges = []
        for u, v, w in edges:
            nu, nv = comp[u], comp[v]
            if nu != nv:
                new_edges.append((nu, nv, w - min_in[v]))
        edges = new_edges
        root = comp[root]
        n = num_comp
    return res

def bidirectional_bfs(begin, end, word_list):
    word_set = set(word_list)
    if end not in word_set: return 0
    front = {begin}
    back = {end}
    visited = {begin, end}
    steps = 1
    while front and back:
        if len(front) > len(back):
            front, back = back, front
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    nw = word[:i] + c + word[i+1:]
                    if nw in back:
                        return steps + 1
                    if nw in word_set and nw not in visited:
                        visited.add(nw)
                        next_front.add(nw)
        front = next_front
        steps += 1
    return 0

def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    backtrack([], nums)
    return result

# permutations([1,2,3]) → [[1,2,3],[1,3,2],...]

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

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

import random

class TreapNode:
    def __init__(self, key):
        self.key = key
        self.pri = random.random()
        self.left = self.right = None
        self.size = 1

def size(t): return t.size if t else 0

def update(t):
    if t: t.size = 1 + size(t.left) + size(t.right)

def split(t, key):
    if not t: return None, None
    if t.key <= key:
        t.right, right = split(t.right, key)
        update(t)
        return t, right
    else:
        left, t.left = split(t.left, key)
        update(t)
        return left, t

def merge(left, right):
    if not left or not right:
        return left or right
    if left.pri > right.pri:
        left.right = merge(left.right, right)
        update(left)
        return left
    else:
        right.left = merge(left, right.left)
        update(right)
        return right

def insert(root, key):
    left, right = split(root, key)
    return merge(merge(left, TreapNode(key)), right)

def erase(root, key):
    left, right = split(root, key)
    left2, _ = split(left, key - 1)
    return merge(left2, right)

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1: return -1
        right = check(node.right)
        if right == -1: return -1
        if abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return check(root) != -1

from collections import deque

def max_flow(graph, source, sink, n):
    # graph[u][v] = capacity
    def bfs(source, sink, parent):
        visited = {source}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in range(n):
                if v not in visited and graph[u][v] > 0:
                    visited.add(v)
                    parent[v] = u
                    if v == sink:
                        return True
                    queue.append(v)
        return False

    total_flow = 0
    parent = [-1] * n
    while bfs(source, sink, parent):
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, graph[u][v])
            v = u
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = u
        total_flow += path_flow
        parent = [-1] * n
    return total_flow

def euler_tour(adj, root=0):
    n = len(adj)
    tin = [0] * n
    tout = [0] * n
    order = []
    timer = [0]

    def dfs(u, parent):
        tin[u] = timer[0]
        order.append(u)
        timer[0] += 1
        for v in adj[u]:
            if v != parent:
                dfs(v, u)
        tout[u] = timer[0] - 1

    dfs(root, -1)
    return tin, tout, order

# Subtree of u = order[tin[u]:tout[u]+1]
# u is ancestor of v iff tin[u] <= tin[v] and tout[v] <= tout[u]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

# gcd(48, 18) → 6
# extended_gcd(48, 18) → (6, -1, 3)  (48*(-1) + 18*3 = 6)

def min_deletions_balanced(s):
    b_count = 0
    deletions = 0
    for c in s:
        if c == 'b':
            b_count += 1
        else:  # c == 'a'
            deletions = min(deletions + 1, b_count)
    return deletions

# min_deletions_balanced("aababbab") → 2
# Delete s[2] and s[6] → "aaabbb"
# min_deletions_balanced("bbaaaaabb") → 2

import math

class SparseTable:
    def __init__(self, arr):
        n = len(arr)
        k = int(math.log2(n)) + 1 if n else 0
        self.table = [[0]*n for _ in range(k)]
        self.table[0] = arr[:]
        for j in range(1, k):
            for i in range(n - (1 << j) + 1):
                self.table[j][i] = min(
                    self.table[j-1][i],
                    self.table[j-1][i + (1 << (j-1))])
        self.log = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log[i] = self.log[i//2] + 1

    def query(self, l, r):  # inclusive
        j = self.log[r - l + 1]
        return min(self.table[j][l],
                   self.table[j][r - (1 << j) + 1])

from collections import deque

def shortest_path(grid, k):
    m, n = len(grid), len(grid[0])
    if m == 1 and n == 1: return 0
    queue = deque([(0, 0, k, 0)])  # row, col, elims left, steps
    visited = set()
    visited.add((0, 0, k))
    while queue:
        r, c, e, steps = queue.popleft()
        for dr, dc in ((0,1),(0,-1),(1,0),(-1,0)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < m and 0 <= nc < n:
                ne = e - grid[nr][nc]
                if nr == m-1 and nc == n-1:
                    return steps + 1
                if ne >= 0 and (nr, nc, ne) not in visited:
                    visited.add((nr, nc, ne))
                    queue.append((nr, nc, ne, steps + 1))
    return -1

from collections import deque, defaultdict

def topological_sort_kahn(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nei in graph[node]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    return order if len(order) == n else []  # empty = cycle

def find_bridges(graph, n):
    disc = [-1] * n
    low = [-1] * n
    parent = [-1] * n
    bridges = []
    timer = [0]

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph[u]:
            if disc[v] == -1:
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return bridges

def next_permutation(nums):
    n = len(nums)
    # Step 1: find rightmost ascent
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # Step 2: find rightmost element > nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # Step 3: reverse suffix
    nums[i+1:] = nums[i+1:][::-1]

# [1,2,3] → [1,3,2]
# [3,2,1] → [1,2,3]
# [1,1,5] → [1,5,1]

import heapq

def swim_in_water(grid):
    n = len(grid)
    visited = [[False]*n for _ in range(n)]
    heap = [(grid[0][0], 0, 0)]
    visited[0][0] = True
    while heap:
        t, r, c = heapq.heappop(heap)
        if r == n-1 and c == n-1:
            return t
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r+dr, c+dc
            if 0<=nr                visited[nr][nc] = True
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
    return -1

# Closed-form
def min_operations(n):
    return n * n // 4

# Step-by-step understanding:
def min_operations_explained(n):
    arr = [2*i + 1 for i in range(n)]
    target = n  # median
    ops = sum(target - x for x in arr if x < target)
    return ops

# min_operations(3) → 2
# [1,3,5] → target 3: move 1→3 (2 ops)
# min_operations(6) → 9
# [1,3,5,7,9,11] → target 6

class BIT_RangeUpdate:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def _update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def range_add(self, l, r, val):
        self._update(l, val)
        if r + 1 <= self.n:
            self._update(r + 1, -val)

    def point_query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

# bit = BIT_RangeUpdate(5)
# bit.range_add(2, 4, 3)  # add 3 to positions 2..4
# [bit.point_query(i) for i in range(1, 6)]
# → [0, 3, 3, 3, 0]

from collections import deque

def pacific_atlantic(heights):
    if not heights: return []
    m, n = len(heights), len(heights[0])
    def bfs(starts):
        reachable = set(starts)
        queue = deque(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                        and (nr,nc) not in reachable
                        and heights[nr][nc] >= heights[r][c]):
                    reachable.add((nr,nc))
                    queue.append((nr,nc))
        return reachable
    pacific = [(r,0) for r in range(m)] + [(0,c) for c in range(1,n)]
    atlantic = [(r,n-1) for r in range(m)] + [(m-1,c) for c in range(n-1)]
    return list(bfs(pacific) & bfs(atlantic))

def permute_unique(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return result

# permute_unique([1, 1, 2])
# → [[1,1,2],[1,2,1],[2,1,1]]

def kruskal(num_nodes, edges):
    # edges = [(weight, u, v), ...]
    edges.sort()
    uf = UnionFind(num_nodes)
    mst = []
    total_weight = 0
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total_weight += w
            if len(mst) == num_nodes - 1:
                break
    return mst, total_weight

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return len(stack) == 0

# is_valid("({[]})") → True
# is_valid("([)]") → False

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        i += 1  # 1-indexed
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def range_query(self, l, r):
        return self.query(r) - (self.query(l-1) if l > 0 else 0)

def my_pow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    result = 1
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

# my_pow(2, 10) → 1024
# my_pow(2, -2) → 0.25

def interval_intersection(A, B):
    i = j = 0
    result = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            result.append([lo, hi])
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

# Greedy (only for canonical denominations)
def min_coins_greedy(coins, amount):
    coins.sort(reverse=True)
    count = 0
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
            result.append(coin)
    return count if amount == 0 else -1

# DP (works for any denominations)
def min_coins_dp(coins, amount):
    dp = [float('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] != float('inf') else -1

# min_coins_greedy([25, 10, 5, 1], 41) → 4 (25+10+5+1)
# min_coins_dp([1, 3, 4], 6) → 2 (3+3)

# Iterative
def my_pow(x, n):
    if n < 0:
        x, n = 1/x, -n
    result = 1
    while n > 0:
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2
    return result

# Recursive
def my_pow_rec(x, n):
    if n == 0: return 1
    if n < 0: return my_pow_rec(1/x, -n)
    half = my_pow_rec(x, n // 2)
    return half * half * (x if n % 2 else 1)

from collections import defaultdict

def accounts_merge(accounts):
    parent = {}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        parent[find(a)] = find(b)
    email_to_name = {}
    for acct in accounts:
        name = acct[0]
        for email in acct[1:]:
            if email not in parent:
                parent[email] = email
            email_to_name[email] = name
            union(acct[1], email)
    groups = defaultdict(list)
    for email in parent:
        groups[find(email)].append(email)
    return [[email_to_name[root]] + sorted(emails)
            for root, emails in groups.items()]

def boundary_traversal(root):
    if not root:
        return []
    result = [root.val]
    def left_boundary(node):
        if not node or (not node.left and not node.right):
            return
        result.append(node.val)
        if node.left:
            left_boundary(node.left)
        else:
            left_boundary(node.right)

    def leaves(node):
        if not node:
            return
        if not node.left and not node.right:
            result.append(node.val)
            return
        leaves(node.left)
        leaves(node.right)

    def right_boundary(node):
        if not node or (not node.left and not node.right):
            return
        if node.right:
            right_boundary(node.right)
        else:
            right_boundary(node.left)
        result.append(node.val)  # bottom-up

    left_boundary(root.left)
    leaves(root.left)
    leaves(root.right)
    right_boundary(root.right)
    return result

def count_distinct_window(arr, k):
    freq = {}
    result = []
    for i in range(len(arr)):
        # Add right element
        freq[arr[i]] = freq.get(arr[i], 0) + 1
        # Remove left element when window exceeds k
        if i >= k:
            left = arr[i - k]
            freq[left] -= 1
            if freq[left] == 0:
                del freq[left]
        # Record result when window is full
        if i >= k - 1:
            result.append(len(freq))
    return result

# count_distinct_window([1,2,1,3,4,2,3], 4)
# → [3, 4, 4, 3]
# Windows: [1,2,1,3]→3, [2,1,3,4]→4, [1,3,4,2]→4, [3,4,2,3]→3

def find_disappeared(nums):
    for x in nums:
        idx = abs(x) - 1
        nums[idx] = -abs(nums[idx])
    return [i + 1 for i in range(len(nums)) if nums[i] > 0]

# Cyclic sort approach
def find_disappeared_cyclic(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    return [i + 1 for i in range(len(nums)) if nums[i] != i + 1]

# find_disappeared([4,3,2,7,8,2,3,1]) → [5, 6]

def calculate2(s):
    stack = []
    num = 0
    op = '+'
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if ch in '+-*/' or i == len(s) - 1:
            if op == '+':
                stack.append(num)
            elif op == '-':
                stack.append(-num)
            elif op == '*':
                stack.append(stack.pop() * num)
            elif op == '/':
                stack.append(int(stack.pop() / num))
            op = ch
            num = 0
    return sum(stack)

# calculate2("3+2*2") → 7

def is_symmetric(root):
    def is_mirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val and
                is_mirror(t1.left, t2.right) and
                is_mirror(t1.right, t2.left))
    return is_mirror(root, root) if root else True

def matrix_chain_order(dims):
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]
    # l = chain length
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = (dp[i][k] + dp[k+1][j]
                        + dims[i] * dims[k+1] * dims[j+1])
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

# dims = [10, 20, 30, 40]
# Matrices: 10x20, 20x30, 30x40
# matrix_chain_order(dims) → 18000

def find_all_cycles(graph, n):
    color = [0] * n  # 0=white, 1=gray, 2=black
    parent = [-1] * n
    cycles = []

    def dfs(u):
        color[u] = 1
        for v in graph[u]:
            if v == parent[u]:
                continue
            if color[v] == 1:
                # Found cycle, trace back
                cycle = [v]
                curr = u
                while curr != v:
                    cycle.append(curr)
                    curr = parent[curr]
                cycle.append(v)
                cycles.append(cycle)
            elif color[v] == 0:
                parent[v] = u
                dfs(v)
        color[u] = 2

    for i in range(n):
        if color[i] == 0:
            dfs(i)
    return cycles

# graph = {0:[1,2], 1:[0,2], 2:[0,1]}
# find_all_cycles(graph, 3) → one triangle cycle

def max_profit_k(k, prices):
    n = len(prices)
    if not n: return 0
    if k >= n // 2:  # unlimited transactions
        return sum(max(0, prices[i+1]-prices[i]) for i in range(n-1))
    dp = [[0] * n for _ in range(k + 1)]
    for t in range(1, k + 1):
        max_prev = -prices[0]
        for i in range(1, n):
            dp[t][i] = max(dp[t][i-1], prices[i] + max_prev)
            max_prev = max(max_prev, dp[t-1][i] - prices[i])
    return dp[k][n-1]

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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

# Output: [[3], [9, 20], [15, 7]]

import random

def reservoir_sample_k(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir

# Weighted reservoir sampling (A-ES algorithm)
def weighted_reservoir(stream, k):
    import heapq
    import math
    heap = []  # min-heap of (key, item)
    for item, weight in stream:
        key = random.random() ** (1.0 / weight)
        if len(heap) < k:
            heapq.heappush(heap, (key, item))
        elif key > heap[0][0]:
            heapq.heapreplace(heap, (key, item))
    return [item for _, item in heap]

# reservoir_sample_k(range(100), 5) → 5 random items

# Closed-form
def min_operations(n):
    return n * n // 4

# Step-by-step understanding:
def min_operations_explained(n):
    arr = [2*i + 1 for i in range(n)]
    target = n  # median
    ops = sum(target - x for x in arr if x < target)
    return ops

# min_operations(3) → 2
# [1,3,5] → target 3: move 1→3 (2 ops)
# min_operations(6) → 9
# [1,3,5,7,9,11] → target 6

def generate_parentheses(n):
    result = []
    def backtrack(path, open_ct, close_ct):
        if len(path) == 2 * n:
            result.append(''.join(path))
            return
        if open_ct < n:
            path.append('(')
            backtrack(path, open_ct + 1, close_ct)
            path.pop()
        if close_ct < open_ct:
            path.append(')')
            backtrack(path, open_ct, close_ct + 1)
            path.pop()
    backtrack([], 0, 0)
    return result

# generate_parentheses(3)
# → ["((()))","(()())","(())()","()(())","()()()"]

def heap_sort(arr):
    n = len(arr)
    def heapify(n, i):
        largest = i
        l, r = 2*i + 1, 2*i + 2
        if l < n and arr[l] > arr[largest]:
            largest = l
        if r < n and arr[r] > arr[largest]:
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(n, largest)
    for i in range(n // 2 - 1, -1, -1):
        heapify(n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(i, 0)
    return arr

class ConvexHullTrick:
    def __init__(self):
        self.lines = []  # (slope, intercept)

    def bad(self, l1, l2, l3):
        # Is l2 unnecessary given l1 and l3?
        return ((l3[1]-l1[1]) * (l1[0]-l2[0])
                <= (l2[1]-l1[1]) * (l1[0]-l3[0]))

    def add_line(self, m, b):
        line = (m, b)
        while (len(self.lines) >= 2 and
               self.bad(self.lines[-2], self.lines[-1], line)):
            self.lines.pop()
        self.lines.append(line)

    def query(self, x):
        lo, hi = 0, len(self.lines) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self.eval(mid, x) > self.eval(mid+1, x):
                lo = mid + 1
            else:
                hi = mid
        return self.eval(lo, x)

    def eval(self, idx, x):
        m, b = self.lines[idx]
        return m * x + b

# cht = ConvexHullTrick()
# cht.add_line(1, 1)  # y = x + 1
# cht.add_line(-1, 5) # y = -x + 5
# cht.query(3) → 2 (min of 4, 2)

def remove_duplicate_letters(s):
    last = {ch: i for i, ch in enumerate(s)}
    stack = []
    in_stack = set()
    for i, ch in enumerate(s):
        if ch in in_stack:
            continue
        while stack and ch < stack[-1] and last[stack[-1]] > i:
            in_stack.remove(stack.pop())
        stack.append(ch)
        in_stack.add(ch)
    return ''.join(stack)

# remove_duplicate_letters("bcabc") → "abc"
# remove_duplicate_letters("cbacdcbc") → "acdb"

def build_tree(preorder, inorder):
    idx_map = {val: i for i, val in enumerate(inorder)}
    pre_idx = [0]

    def build(lo, hi):
        if lo > hi:
            return None
        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)
        mid = idx_map[root_val]
        root.left = build(lo, mid - 1)
        root.right = build(mid + 1, hi)
        return root

    return build(0, len(inorder) - 1)

class LazySegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def push_down(self, node, l, r):
        if self.lazy[node]:
            mid = (l + r) // 2
            for child, size in [(2*node, mid-l+1), (2*node+1, r-mid)]:
                self.tree[child] += self.lazy[node] * size
                self.lazy[child] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, node, l, r, ql, qr, val):
        if ql <= l and r <= qr:
            self.tree[node] += val * (r - l + 1)
            self.lazy[node] += val
            return
        self.push_down(node, l, r)
        mid = (l + r) // 2
        if ql <= mid: self.update(2*node, l, mid, ql, qr, val)
        if qr > mid: self.update(2*node+1, mid+1, r, ql, qr, val)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, node, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.tree[node]
        self.push_down(node, l, r)
        mid = (l + r) // 2
        res = 0
        if ql <= mid: res += self.query(2*node, l, mid, ql, qr)
        if qr > mid: res += self.query(2*node+1, mid+1, r, ql, qr)
        return res

# XOR approach: XOR all indices and values
def missing_number_xor(nums):
    xor = len(nums)
    for i, num in enumerate(nums):
        xor ^= i ^ num
    return xor

# Math approach: expected - actual
def missing_number_math(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

# missing_number([3,0,1]) → 2

def largest_rectangle(heights):
    stack = []
    max_area = 0
    heights.append(0)  # sentinel
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()
    return max_area

# largest_rectangle([2,1,5,6,2,3]) → 10

def solve_2sat(n, clauses):
    # n variables (0..n-1), neg of x = x+n
    graph = [[] for _ in range(2*n)]
    rgraph = [[] for _ in range(2*n)]
    def neg(x): return x+n if x < n else x-n
    for a, b in clauses:  # (a OR b)
        graph[neg(a)].append(b)
        graph[neg(b)].append(a)
        rgraph[b].append(neg(a))
        rgraph[a].append(neg(b))
    # Kosaraju's SCC
    visited = [False]*(2*n)
    order = []
    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]: dfs1(v)
        order.append(u)
    for i in range(2*n):
        if not visited[i]: dfs1(i)
    comp = [-1]*(2*n)
    c = 0
    def dfs2(u, c):
        comp[u] = c
        for v in rgraph[u]:
            if comp[v] == -1: dfs2(v, c)
    for u in reversed(order):
        if comp[u] == -1:
            dfs2(u, c)
            c += 1
    for i in range(n):
        if comp[i] == comp[i+n]: return None
    return [comp[i] > comp[i+n] for i in range(n)]

def min_cost_path(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(m):
        dp[0] = dp[0] + grid[i][0]
        for j in range(1, n):
            if i == 0:
                dp[j] = dp[j-1] + grid[i][j]
            else:
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
    return dp[n-1]

# grid = [[1, 3, 1],
#         [1, 5, 1],
#         [4, 2, 1]]
# min_cost_path(grid) → 7 (1→3→1→1→1)

class SegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = arr[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def query(self, l, r):  # [l, r)
        res = 0
        l += self.n; r += self.n
        while l < r:
            if l & 1: res += self.tree[l]; l += 1
            if r & 1: r -= 1; res += self.tree[r]
            l //= 2; r //= 2
        return res

def max_subarray(arr):
    max_ending_here = arr[0]
    max_so_far = arr[0]
    for num in arr[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

from collections import deque

def bfs_01(graph, src, n):
    dist = [float('inf')] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:  # w is 0 or 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

def find_all_cycles(graph, n):
    color = [0] * n  # 0=white, 1=gray, 2=black
    parent = [-1] * n
    cycles = []

    def dfs(u):
        color[u] = 1
        for v in graph[u]:
            if v == parent[u]:
                continue
            if color[v] == 1:
                # Found cycle, trace back
                cycle = [v]
                curr = u
                while curr != v:
                    cycle.append(curr)
                    curr = parent[curr]
                cycle.append(v)
                cycles.append(cycle)
            elif color[v] == 0:
                parent[v] = u
                dfs(v)
        color[u] = 2

    for i in range(n):
        if color[i] == 0:
            dfs(i)
    return cycles

# graph = {0:[1,2], 1:[0,2], 2:[0,1]}
# find_all_cycles(graph, 3) → one triangle cycle

def longest_valid_parentheses(s):
    stack = [-1]
    max_len = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

# longest_valid_parentheses(")()())") → 4
# longest_valid_parentheses("()(()") → 2

def get_intersection_node(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a

def insert_interval(intervals, new):
    result = []
    i = 0
    n = len(intervals)
    # Add all intervals ending before new starts
    while i < n and intervals[i][1] < new[0]:
        result.append(intervals[i])
        i += 1
    # Merge overlapping intervals with new
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    result.append(new)
    # Add remaining
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

# Extended GCD: returns (g, x, y) where ax + by = g
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

# from math import gcd, lcm  # Python 3.9+

def count_scc(graph, n):
    disc = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    timer = [0]
    sccs = []

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        stack.append(u)
        on_stack[u] = True
        for v in graph[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            scc = []
            while True:
                v = stack.pop()
                on_stack[v] = False
                scc.append(v)
                if v == u:
                    break
            sccs.append(scc)

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return sccs

# graph = {0:[1], 1:[2], 2:[0,3], 3:[4], 4:[5], 5:[3]}
# count_scc(graph, 6) → [[3,5,4],[0,2,1]]

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

# product_except_self([1,2,3,4]) → [24,12,8,6]

def kth_smallest(root, k):
    stack = []
    curr = root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right

import heapq

def min_refuel_stops(target, start_fuel, stations):
    heap = []  # max-heap (negate fuel)
    fuel = start_fuel
    stops = 0
    prev = 0
    for pos, gas in stations + [(target, 0)]:
        fuel -= (pos - prev)
        while heap and fuel < 0:
            fuel += -heapq.heappop(heap)
            stops += 1
        if fuel < 0:
            return -1
        heapq.heappush(heap, -gas)
        prev = pos
    return stops

from collections import defaultdict, deque

def calc_equation(equations, values, queries):
    graph = defaultdict(dict)
    for (a, b), v in zip(equations, values):
        graph[a][b] = v
        graph[b][a] = 1.0 / v

    def bfs(src, dst):
        if src not in graph or dst not in graph:
            return -1.0
        if src == dst:
            return 1.0
        visited = {src}
        queue = deque([(src, 1.0)])
        while queue:
            node, prod = queue.popleft()
            for nb, w in graph[node].items():
                if nb == dst:
                    return prod * w
                if nb not in visited:
                    visited.add(nb)
                    queue.append((nb, prod * w))
        return -1.0

    return [bfs(a, b) for a, b in queries]

# equations = [["a","b"],["b","c"]], values = [2.0, 3.0]
# queries = [["a","c"],["b","a"],["a","e"]]
# → [6.0, 0.5, -1.0]

class RollingHash:
    def __init__(self, s, base=31, mod=10**9+9):
        self.mod = mod
        self.base = base
        n = len(s)
        self.h = [0] * (n + 1)
        self.pw = [1] * (n + 1)
        for i in range(n):
            self.h[i+1] = (self.h[i] * base + ord(s[i])) % mod
            self.pw[i+1] = self.pw[i] * base % mod

    def get_hash(self, l, r):
        # Hash of s[l:r+1]
        return (self.h[r+1] - self.h[l] * self.pw[r-l+1]) % self.mod

def find_pattern(text, pattern):
    rh_t = RollingHash(text)
    rh_p = RollingHash(pattern)
    ph = rh_p.get_hash(0, len(pattern)-1)
    m = len(pattern)
    return [i for i in range(len(text)-m+1)
            if rh_t.get_hash(i, i+m-1) == ph]

# find_pattern("abcabcabc", "abc") → [0, 3, 6]

import heapq

class MedianMaintenance:
    def __init__(self):
        self.lo = []  # max-heap (negate values)
        self.hi = []  # min-heap

    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

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

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

# search_rotated([4,5,6,7,0,1,2], 0) → 4
# search_rotated([4,5,6,7,0,1,2], 3) → -1

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

# weights = [1, 3, 4, 5]
# values  = [10, 40, 50, 70]
# unbounded_knapsack(weights, values, 8) → 110
# (two items of weight 4 → 50+50, or weight 3+5 → 40+70=110)

class HLD:
    def __init__(self, adj, root=0):
        n = len(adj)
        self.parent = [0]*n
        self.depth = [0]*n
        self.heavy = [-1]*n
        self.head = [0]*n
        self.pos = [0]*n
        self.sz = [1]*n
        # DFS to compute subtree sizes and heavy children
        stack = [(root, -1, False)]
        order = []
        while stack:
            u, p, visited = stack.pop()
            if visited:
                for v in adj[u]:
                    if v != p:
                        self.sz[u] += self.sz[v]
                        if self.heavy[u]==-1 or self.sz[v]>self.sz[self.heavy[u]]:
                            self.heavy[u] = v
                continue
            self.parent[u] = p
            stack.append((u, p, True))
            for v in adj[u]:
                if v != p:
                    self.depth[v] = self.depth[u]+1
                    stack.append((v, u, False))
        # Decompose into chains
        cur_pos = 0
        stack = [(root, root)]
        while stack:
            u, h = stack.pop()
            self.head[u] = h
            self.pos[u] = cur_pos
            cur_pos += 1
            # Process light children first (so heavy is processed last = next on stack)
            children = [v for v in adj[u] if v!=self.parent[u] and v!=self.heavy[u]]
            for v in children:
                stack.append((v, v))
            if self.heavy[u] != -1:
                stack.append((self.heavy[u], h))

class MyCircularQueue:
    def __init__(self, k):
        self.data = [0] * k
        self.size = k
        self.head = 0
        self.count = 0

    def enQueue(self, value):
        if self.isFull(): return False
        tail = (self.head + self.count) % self.size
        self.data[tail] = value
        self.count += 1
        return True

    def deQueue(self):
        if self.isEmpty(): return False
        self.head = (self.head + 1) % self.size
        self.count -= 1
        return True

    def Front(self):
        return -1 if self.isEmpty() else self.data[self.head]

    def Rear(self):
        if self.isEmpty(): return -1
        tail = (self.head + self.count - 1) % self.size
        return self.data[tail]

    def isEmpty(self): return self.count == 0
    def isFull(self): return self.count == self.size

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)   # userId → [(time, tweetId)]
        self.follows = defaultdict(set)   # userId → {followeeIds}

    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.time, tweetId))
        self.time -= 1  # negative for max-heap via min-heap

    def getNewsFeed(self, userId):
        heap = []
        self.follows[userId].add(userId)
        for uid in self.follows[userId]:
            if self.tweets[uid]:
                idx = len(self.tweets[uid]) - 1
                t, tid = self.tweets[uid][idx]
                heapq.heappush(heap, (t, tid, uid, idx))
        feed = []
        while heap and len(feed) < 10:
            t, tid, uid, idx = heapq.heappop(heap)
            feed.append(tid)
            if idx > 0:
                t2, tid2 = self.tweets[uid][idx-1]
                heapq.heappush(heap, (t2, tid2, uid, idx-1))
        return feed

    def follow(self, followerId, followeeId):
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        self.follows[followerId].discard(followeeId)

def is_valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    visited = set()
    def dfs(node, parent):
        visited.add(node)
        for nei in adj[node]:
            if nei == parent: continue
            if nei in visited: return False
            if not dfs(nei, node): return False
        return True
    return dfs(0, -1) and len(visited) == n

import bisect

class MyCalendar:
    def __init__(self):
        self.starts = []
        self.ends = []

    def book(self, start, end):
        i = bisect.bisect_right(self.starts, start)
        if i > 0 and self.ends[i-1] > start:
            return False
        if i < len(self.starts) and self.starts[i] < end:
            return False
        self.starts.insert(i, start)
        self.ends.insert(i, end)
        return True

# cal = MyCalendar()
# cal.book(10, 20) → True
# cal.book(15, 25) → False (overlap)
# cal.book(20, 30) → True

from collections import deque

def find_min_height_trees(n, edges):
    if n <= 2:
        return list(range(n))
    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    leaves = deque(i for i in range(n) if len(adj[i]) == 1)
    remaining = n
    while remaining > 2:
        new_leaves = []
        remaining -= len(leaves)
        for leaf in leaves:
            neighbor = adj[leaf].pop()
            adj[neighbor].remove(leaf)
            if len(adj[neighbor]) == 1:
                new_leaves.append(neighbor)
        leaves = deque(new_leaves)
    return list(leaves)

def solve_2sat(n, clauses):
    # n variables (0..n-1), neg of x = x+n
    graph = [[] for _ in range(2*n)]
    rgraph = [[] for _ in range(2*n)]
    def neg(x): return x+n if x < n else x-n
    for a, b in clauses:  # (a OR b)
        graph[neg(a)].append(b)
        graph[neg(b)].append(a)
        rgraph[b].append(neg(a))
        rgraph[a].append(neg(b))
    # Kosaraju's SCC
    visited = [False]*(2*n)
    order = []
    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]: dfs1(v)
        order.append(u)
    for i in range(2*n):
        if not visited[i]: dfs1(i)
    comp = [-1]*(2*n)
    c = 0
    def dfs2(u, c):
        comp[u] = c
        for v in rgraph[u]:
            if comp[v] == -1: dfs2(v, c)
    for u in reversed(order):
        if comp[u] == -1:
            dfs2(u, c)
            c += 1
    for i in range(n):
        if comp[i] == comp[i+n]: return None
    return [comp[i] > comp[i+n] for i in range(n)]

def is_interleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3): return False
    dp = [False] * (n + 1)
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 and j == 0:
                dp[j] = True
            elif i == 0:
                dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
            elif j == 0:
                dp[j] = dp[j] and s1[i-1] == s3[i-1]
            else:
                dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or \
                        (dp[j-1] and s2[j-1] == s3[i+j-1])
    return dp[n]

def is_symmetric(root):
    def is_mirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val and
                is_mirror(t1.left, t2.right) and
                is_mirror(t1.right, t2.left))
    return is_mirror(root, root) if root else True

# Iterative
def my_pow(x, n):
    if n < 0:
        x, n = 1/x, -n
    result = 1
    while n > 0:
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2
    return result

# Recursive
def my_pow_rec(x, n):
    if n == 0: return 1
    if n < 0: return my_pow_rec(1/x, -n)
    half = my_pow_rec(x, n // 2)
    return half * half * (x if n % 2 else 1)

def find_maximum_xor(nums):
    max_xor = 0
    mask = 0
    for i in range(31, -1, -1):
        mask |= (1 << i)
        prefixes = {n & mask for n in nums}
        candidate = max_xor | (1 << i)
        for p in prefixes:
            if p ^ candidate in prefixes:
                max_xor = candidate
                break
    return max_xor

class Codec:
    def encode(self, strs):
        return ''.join(f'{len(s)}#{s}' for s in strs)

    def decode(self, s):
        result = []
        i = 0
        while i < len(s):
            j = s.index('#', i)
            length = int(s[i:j])
            result.append(s[j+1:j+1+length])
            i = j + 1 + length
        return result

# encode(["hello","world"]) → "5#hello5#world"

def sort_list(head):
    if not head or not head.next:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left = sort_list(head)
    right = sort_list(mid)
    return merge(left, right)

def merge(l1, l2):
    dummy = curr = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

import bisect
import hashlib

class ConsistentHash:
    def __init__(self, replicas=150):
        self.replicas = replicas
        self.ring = []       # sorted hash positions
        self.node_map = {}   # hash → node name

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            bisect.insort(self.ring, h)
            self.node_map[h] = node

    def remove_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            self.ring.remove(h)
            del self.node_map[h]

    def get_node(self, key):
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h) % len(self.ring)
        return self.node_map[self.ring[idx]]

# ch = ConsistentHash(replicas=3)
# ch.add_node("server1")
# ch.add_node("server2")
# ch.get_node("my_key") → "server1" or "server2"

def z_function(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

def z_search(text, pattern):
    combined = pattern + '$' + text
    z = z_function(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m+1, len(combined)) if z[i] == m]

from collections import Counter

def find_anagrams(s, p):
    if len(p) > len(s): return []
    p_count = Counter(p)
    s_count = Counter(s[:len(p)])
    result = []
    if s_count == p_count:
        result.append(0)
    for i in range(len(p), len(s)):
        s_count[s[i]] += 1
        left = s[i - len(p)]
        s_count[left] -= 1
        if s_count[left] == 0:
            del s_count[left]
        if s_count == p_count:
            result.append(i - len(p) + 1)
    return result

# find_anagrams("cbaebabacd", "abc") → [0, 6]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

# Extended GCD: returns (g, x, y) where ax + by = g
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

# from math import gcd, lcm  # Python 3.9+

def max_independent_set(adj, weights, root=0):
    n = len(adj)
    inc = [0] * n  # include this node
    exc = [0] * n  # exclude this node
    visited = [False] * n

    def dfs(u):
        visited[u] = True
        inc[u] = weights[u]
        exc[u] = 0
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
                inc[u] += exc[v]
                exc[u] += max(inc[v], exc[v])

    dfs(root)
    return max(inc[root], exc[root])

# Tree: 0-1, 0-2, 1-3, 1-4
# adj = [[1,2],[0,3,4],[0],[1],[1]]
# weights = [1, 6, 3, 4, 5]
# max_independent_set(adj, weights) → 12 (nodes 2,3,4)

class Codec:
    def encode(self, strs):
        return ''.join(f'{len(s)}#{s}' for s in strs)

    def decode(self, s):
        result = []
        i = 0
        while i < len(s):
            j = s.index('#', i)
            length = int(s[i:j])
            result.append(s[j+1:j+1+length])
            i = j + 1 + length
        return result

# encode(["hello","world"]) → "5#hello5#world"

# Iterative
def my_pow(x, n):
    if n < 0:
        x, n = 1/x, -n
    result = 1
    while n > 0:
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2
    return result

# Recursive
def my_pow_rec(x, n):
    if n == 0: return 1
    if n < 0: return my_pow_rec(1/x, -n)
    half = my_pow_rec(x, n // 2)
    return half * half * (x if n % 2 else 1)

from bisect import bisect_left, insort

def max_sum_submatrix(matrix, k):
    m, n = len(matrix), len(matrix[0])
    result = float('-inf')
    for left in range(n):
        row_sum = [0] * m
        for right in range(left, n):
            for r in range(m):
                row_sum[r] += matrix[r][right]
            # Find max subarray sum <= k
            sorted_sums = [0]
            prefix = 0
            for s in row_sum:
                prefix += s
                idx = bisect_left(sorted_sums, prefix - k)
                if idx < len(sorted_sums):
                    result = max(result, prefix - sorted_sums[idx])
                insort(sorted_sums, prefix)
    return result

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

# product_except_self([1,2,3,4]) → [24,12,8,6]

def has_cycle_directed(graph, n):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(u):
        color[u] = GRAY
        for v in graph.get(u, []):
            if color[v] == GRAY:
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(color[u] == WHITE and dfs(u) for u in range(n))

def generate_spiral(n):
    matrix = [[0] * n for _ in range(n)]
    num = 1
    top, bottom, left, right = 0, n-1, 0, n-1
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            matrix[top][j] = num; num += 1
        top += 1
        for i in range(top, bottom + 1):
            matrix[i][right] = num; num += 1
        right -= 1
        if top <= bottom:
            for j in range(right, left - 1, -1):
                matrix[bottom][j] = num; num += 1
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num; num += 1
            left += 1
    return matrix

# generate_spiral(3)
# → [[1,2,3],[8,9,4],[7,6,5]]

def longest_common_prefix(strs):
    if not strs:
        return ""
    for i in range(len(strs[0])):
        ch = strs[0][i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != ch:
                return strs[0][:i]
    return strs[0]

# longest_common_prefix(["flower","flow","flight"]) → "fl"

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def longest_k_distinct(s, k):
    freq = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

# longest_k_distinct("eceba", 2) → 3 ("ece")
# longest_k_distinct("aa", 1) → 2

# Bucket Sort approach - O(n)
from collections import Counter
def top_k_frequent(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):
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result

# top_k_frequent([1,1,1,2,2,3], 2) → [1, 2]

from bisect import bisect_right

def job_scheduling(start, end, profit):
    jobs = sorted(zip(end, start, profit))
    ends = [j[0] for j in jobs]
    n = len(jobs)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        e, s, p = jobs[i-1]
        # Find latest job ending <= start of current job
        k = bisect_right(ends, s, 0, i) 
        dp[i] = max(dp[i-1], dp[k] + p)
    return dp[n]

# job_scheduling([1,2,3,3],[3,4,5,6],[50,10,40,70]) → 120

def single_number_ii(nums):
    ones = twos = 0
    for n in nums:
        ones = (ones ^ n) & ~twos
        twos = (twos ^ n) & ~ones
    return ones

# General approach: count each bit mod 3
def single_number_ii_general(nums):
    result = 0
    for i in range(32):
        bit_sum = sum((n >> i) & 1 for n in nums)
        if bit_sum % 3:
            result |= 1 << i
    if result >= 2**31:
        result -= 2**32
    return result

# single_number_ii([2,2,3,2]) → 3

def min_falling_path_sum(matrix):
    n = len(matrix)
    dp = matrix[0][:]
    for i in range(1, n):
        new_dp = [0] * n
        for j in range(n):
            left = dp[j-1] if j > 0 else float('inf')
            mid = dp[j]
            right = dp[j+1] if j < n-1 else float('inf')
            new_dp[j] = matrix[i][j] + min(left, mid, right)
        dp = new_dp
    return min(dp)

# min_falling_path_sum([[2,1,3],[6,5,4],[7,8,9]]) → 13
# Path: 1 → 5 → 7

def longest_k_distinct(s, k):
    freq = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

# longest_k_distinct("eceba", 2) → 3 ("ece")
# longest_k_distinct("aa", 1) → 2

class Node:
    def __init__(self, val=0, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten(head):
    curr = head
    while curr:
        if curr.child:
            child_head = curr.child
            # Find tail of child list
            child_tail = child_head
            while child_tail.next:
                child_tail = child_tail.next
            # Splice child list
            nxt = curr.next
            curr.next = child_head
            child_head.prev = curr
            curr.child = None
            child_tail.next = nxt
            if nxt:
                nxt.prev = child_tail
        curr = curr.next
    return head

def max_path_sum(root):
    result = [float('-inf')]
    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        result[0] = max(result[0], node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return result[0]

def get_intersection_node(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a

def length_of_longest_substring(s):
    seen = {}
    left = max_len = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len

# length_of_longest_substring("abcabcbb") → 3 ("abc")

def find_longest_chain(pairs):
    pairs.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for a, b in pairs:
        if a > end:
            count += 1
            end = b
    return count

# find_longest_chain([[1,2],[2,3],[3,4]]) → 2
# Pick [1,2],[3,4]

def permute_unique(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return result

# permute_unique([1, 1, 2])
# → [[1,1,2],[1,2,1],[2,1,1]]

from collections import deque

def shortest_distance(grid):
    m, n = len(grid), len(grid[0])
    dist_sum = [[0]*n for _ in range(m)]
    reach_count = [[0]*n for _ in range(m)]
    buildings = 0

    for si in range(m):
        for sj in range(n):
            if grid[si][sj] == 1:
                buildings += 1
                visited = [[False]*n for _ in range(m)]
                queue = deque([(si, sj, 0)])
                visited[si][sj] = True
                while queue:
                    r, c, d = queue.popleft()
                    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                        nr, nc = r+dr, c+dc
                        if (0 <= nr < m and 0 <= nc < n
                            and not visited[nr][nc]
                            and grid[nr][nc] == 0):
                            visited[nr][nc] = True
                            dist_sum[nr][nc] += d + 1
                            reach_count[nr][nc] += 1
                            queue.append((nr, nc, d+1))

    result = float('inf')
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0 and reach_count[i][j] == buildings:
                result = min(result, dist_sum[i][j])
    return result if result != float('inf') else -1

# 0=empty, 1=building, 2=obstacle

import heapq

def max_events(events):
    events.sort()
    heap = []
    i = 0
    n = len(events)
    attended = 0
    day = 1
    while i < n or heap:
        if not heap:
            day = events[i][0]
        while i < n and events[i][0] <= day:
            heapq.heappush(heap, events[i][1])
            i += 1
        # Remove expired events
        while heap and heap[0] < day:
            heapq.heappop(heap)
        if heap:
            heapq.heappop(heap)  # attend
            attended += 1
        day += 1
    return attended

# max_events([[1,2],[2,3],[3,4]]) → 3
# max_events([[1,2],[2,3],[3,4],[1,2]]) → 4

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for s, e in intervals:
        if s >= end:
            end = e
        else:
            count += 1
    return count

# erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]) → 1

def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        w = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, w * h)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

# max_area([1,8,6,2,5,4,8,3,7]) → 49

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left or right

def lca_bst(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

def find_all_cycles(graph, n):
    color = [0] * n  # 0=white, 1=gray, 2=black
    parent = [-1] * n
    cycles = []

    def dfs(u):
        color[u] = 1
        for v in graph[u]:
            if v == parent[u]:
                continue
            if color[v] == 1:
                # Found cycle, trace back
                cycle = [v]
                curr = u
                while curr != v:
                    cycle.append(curr)
                    curr = parent[curr]
                cycle.append(v)
                cycles.append(cycle)
            elif color[v] == 0:
                parent[v] = u
                dfs(v)
        color[u] = 2

    for i in range(n):
        if color[i] == 0:
            dfs(i)
    return cycles

# graph = {0:[1,2], 1:[0,2], 2:[0,1]}
# find_all_cycles(graph, 3) → one triangle cycle

def reorder_list(head):
    if not head or not head.next:
        return
    # 1. Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # 2. Reverse second half
    prev = None
    curr = slow.next
    slow.next = None
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    # 3. Merge alternately
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

# 1→2→3→4→5 becomes 1→5→2→4→3

def max_subarray_circular(nums):
    max_sum = cur_max = float('-inf')
    min_sum = cur_min = float('inf')
    total = 0
    for x in nums:
        cur_max = max(x, cur_max + x)
        max_sum = max(max_sum, cur_max)
        cur_min = min(x, cur_min + x)
        min_sum = min(min_sum, cur_min)
        total += x
    # If all negative, max_sum is the answer
    if total == min_sum:
        return max_sum
    return max(max_sum, total - min_sum)

# max_subarray_circular([5, -3, 5]) → 10

def min_platforms(arrivals, departures):
    arrivals.sort()
    departures.sort()
    platforms = max_platforms = 0
    i = j = 0
    while i < len(arrivals):
        if arrivals[i] <= departures[j]:
            platforms += 1
            max_platforms = max(max_platforms, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return max_platforms

# Equivalent: line sweep with +1/-1 events

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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

# Output: [[3], [9, 20], [15, 7]]

def num_distinct(s, t):
    m, n = len(s), len(t)
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, m + 1):
        for j in range(n, 0, -1):
            if s[i-1] == t[j-1]:
                dp[j] += dp[j-1]
    return dp[n]

# num_distinct("rabbbit", "rabbit") → 3

def count_primes(n):
    if n < 3:
        return 0
    is_prime = bytearray(b'\x01') * n
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
    return sum(is_prime)

# Segmented sieve for large ranges
def segmented_sieve(lo, hi):
    import math
    limit = int(math.sqrt(hi)) + 1
    primes = []
    sieve = [True] * (limit + 1)
    for i in range(2, limit + 1):
        if sieve[i]:
            primes.append(i)
            for j in range(i*i, limit+1, i):
                sieve[j] = False
    is_prime = [True] * (hi - lo + 1)
    for p in primes:
        start = max(p*p, ((lo + p - 1) // p) * p)
        for j in range(start, hi+1, p):
            is_prime[j - lo] = False
    if lo <= 1:
        is_prime[1 - lo] = False
    return [i + lo for i in range(hi - lo + 1) if is_prime[i]]

# count_primes(100) → 25

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

def subsets_iter(nums):
    result = [[]]
    for num in nums:
        result += [s + [num] for s in result]
    return result

def subsets_bitmask(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

import heapq

def min_cost_connect_points(points):
    n = len(points)
    visited = [False] * n
    heap = [(0, 0)]  # (cost, point_idx)
    total = 0
    edges_used = 0
    while edges_used < n:
        cost, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        total += cost
        edges_used += 1
        for v in range(n):
            if not visited[v]:
                dist = (abs(points[u][0]-points[v][0])
                      + abs(points[u][1]-points[v][1]))
                heapq.heappush(heap, (dist, v))
    return total

def tarjan_scc(graph, n):
    idx = [0]
    stack = []
    on_stack = [False] * n
    index = [-1] * n
    lowlink = [-1] * n
    sccs = []

    def strongconnect(v):
        index[v] = lowlink[v] = idx[0]
        idx[0] += 1
        stack.append(v)
        on_stack[v] = True
        for w in graph.get(v, []):
            if index[w] == -1:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif on_stack[w]:
                lowlink[v] = min(lowlink[v], index[w])
        if lowlink[v] == index[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)

    for v in range(n):
        if index[v] == -1:
            strongconnect(v)
    return sccs

def build_prefix_sum(arr):
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

# arr = [1, 2, 3, 4, 5]
# prefix = [0, 1, 3, 6, 10, 15]
# range_sum(prefix, 1, 3) → 9  (2+3+4)

from math import gcd
from collections import defaultdict

def max_points(points):
    n = len(points)
    if n <= 2: return n
    best = 2
    for i in range(n):
        slopes = defaultdict(int)
        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            g = gcd(abs(dx), abs(dy))
            if g: dx, dy = dx // g, dy // g
            if dx < 0: dx, dy = -dx, -dy
            if dx == 0: dy = abs(dy)
            slopes[(dx, dy)] += 1
        if slopes:
            best = max(best, max(slopes.values()) + 1)
    return best

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.cap = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

def largest_rectangle(heights):
    stack = []
    max_area = 0
    heights.append(0)  # sentinel
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()
    return max_area

# largest_rectangle([2,1,5,6,2,3]) → 10

def search_matrix(matrix, target):
    if not matrix:
        return False
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

# Variant: rows sorted, first elem > last of prev row
# search_matrix([[1,3,5],[10,11,16],[23,30,34]], 3) → True

# Variant II: rows and cols sorted independently
def search_matrix_ii(matrix, target):
    r, c = 0, len(matrix[0]) - 1
    while r < len(matrix) and c >= 0:
        if matrix[r][c] == target:
            return True
        elif matrix[r][c] > target:
            c -= 1
        else:
            r += 1
    return False

def solve_2sat(n, clauses):
    # n variables (0..n-1), neg of x = x+n
    graph = [[] for _ in range(2*n)]
    rgraph = [[] for _ in range(2*n)]
    def neg(x): return x+n if x < n else x-n
    for a, b in clauses:  # (a OR b)
        graph[neg(a)].append(b)
        graph[neg(b)].append(a)
        rgraph[b].append(neg(a))
        rgraph[a].append(neg(b))
    # Kosaraju's SCC
    visited = [False]*(2*n)
    order = []
    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]: dfs1(v)
        order.append(u)
    for i in range(2*n):
        if not visited[i]: dfs1(i)
    comp = [-1]*(2*n)
    c = 0
    def dfs2(u, c):
        comp[u] = c
        for v in rgraph[u]:
            if comp[v] == -1: dfs2(v, c)
    for u in reversed(order):
        if comp[u] == -1:
            dfs2(u, c)
            c += 1
    for i in range(n):
        if comp[i] == comp[i+n]: return None
    return [comp[i] > comp[i+n] for i in range(n)]

from collections import deque

def max_flow(graph, source, sink, n):
    # graph[u][v] = capacity
    def bfs(source, sink, parent):
        visited = {source}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in range(n):
                if v not in visited and graph[u][v] > 0:
                    visited.add(v)
                    parent[v] = u
                    if v == sink:
                        return True
                    queue.append(v)
        return False

    total_flow = 0
    parent = [-1] * n
    while bfs(source, sink, parent):
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, graph[u][v])
            v = u
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = u
        total_flow += path_flow
        parent = [-1] * n
    return total_flow

def is_valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    visited = set()
    def dfs(node, parent):
        visited.add(node)
        for nei in adj[node]:
            if nei == parent: continue
            if nei in visited: return False
            if not dfs(nei, node): return False
        return True
    return dfs(0, -1) and len(visited) == n

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

# max_profit([7,1,5,3,6,4]) → 5 (buy@1, sell@6)

def bucket_sort(arr, num_buckets=10):
    if not arr:
        return arr
    min_val, max_val = min(arr), max(arr)
    bucket_range = (max_val - min_val) / num_buckets + 1
    buckets = [[] for _ in range(num_buckets)]
    for x in arr:
        idx = int((x - min_val) / bucket_range)
        buckets[idx].append(x)
    result = []
    for bucket in buckets:
        result.extend(sorted(bucket))
    return result

# bucket_sort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47])

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, inv_l = count_inversions(arr[:mid])
    right, inv_r = count_inversions(arr[mid:])
    merged = []
    inversions = inv_l + inv_r
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inversions += len(left) - i
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

# _, inv = count_inversions([2, 4, 1, 3, 5])
# inv → 3 (pairs: (2,1), (4,1), (4,3))

from collections import deque

def ladder_length(begin, end, word_list):
    word_set = set(word_list)
    if end not in word_set:
        return 0
    queue = deque([(begin, 1)])
    visited = {begin}
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word == end:
                    return steps + 1
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))
    return 0

# ladder_length("hit","cog",["hot","dot","dog","lot","log","cog"])
# → 5: hit→hot→dot→dog→cog

def generate_parentheses(n):
    result = []
    def backtrack(path, open_ct, close_ct):
        if len(path) == 2 * n:
            result.append(''.join(path))
            return
        if open_ct < n:
            path.append('(')
            backtrack(path, open_ct + 1, close_ct)
            path.pop()
        if close_ct < open_ct:
            path.append(')')
            backtrack(path, open_ct, close_ct + 1)
            path.pop()
    backtrack([], 0, 0)
    return result

# generate_parentheses(3)
# → ["((()))","(()())","(())()","()(())","()()()"]

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return len(stack) == 0

# is_valid("({[]})") → True
# is_valid("([)]") → False

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev = None
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    # Compare halves
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

def merge_stones(stones, K):
    n = len(stones)
    if (n - 1) % (K - 1) != 0: return -1
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    INF = float('inf')
    dp = [[0]*n for _ in range(n)]
    for length in range(K, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = INF
            for mid in range(i, j, K - 1):
                dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid+1][j])
            if (length - 1) % (K - 1) == 0:
                dp[i][j] += prefix[j+1] - prefix[i]
    return dp[0][n-1]

def next_permutation(nums):
    n = len(nums)
    # Step 1: find rightmost ascent
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # Step 2: find rightmost element > nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # Step 3: reverse suffix
    nums[i+1:] = nums[i+1:][::-1]

# [1,2,3] → [1,3,2]
# [3,2,1] → [1,2,3]
# [1,1,5] → [1,5,1]

def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return None

def activity_selection(activities):
    # activities = [(start, end), ...]
    activities.sort(key=lambda x: x[1])
    selected = [activities[0]]
    last_end = activities[0][1]
    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

# activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
# activity_selection(activities)
# → [(1,4),(5,7),(8,11),(12,16)]

def find_min_rotated(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

# With duplicates
def find_min_rotated_dup(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            hi = mid
        else:
            hi -= 1  # can't decide, shrink
    return nums[lo]

# find_min_rotated([3,4,5,1,2]) → 1
# find_min_rotated_dup([2,2,2,0,1]) → 0

def longest_str_chain(words):
    words.sort(key=len)
    dp = {}
    best = 1
    for word in words:
        dp[word] = 1
        for i in range(len(word)):
            prev = word[:i] + word[i+1:]
            if prev in dp:
                dp[word] = max(dp[word], dp[prev] + 1)
        best = max(best, dp[word])
    return best

# longest_str_chain(["a","b","ba","bca","bda","bdca"]) → 4
# "a" → "ba" → "bda" → "bdca"

def counting_sort(arr):
    if not arr:
        return arr
    min_val, max_val = min(arr), max(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    result = []
    for i, c in enumerate(count):
        result.extend([i + min_val] * c)
    return result

class IPTrie:
    def __init__(self):
        self.children = [None, None]
        self.value = None  # next-hop info

    def insert(self, ip_int, prefix_len, value):
        node = self
        for i in range(31, 31 - prefix_len, -1):
            bit = (ip_int >> i) & 1
            if node.children[bit] is None:
                node.children[bit] = IPTrie()
            node = node.children[bit]
        node.value = value

    def lookup(self, ip_int):
        node = self
        best = None
        for i in range(31, -1, -1):
            bit = (ip_int >> i) & 1
            if node.children[bit] is None:
                break
            node = node.children[bit]
            if node.value is not None:
                best = node.value
        return best

def ip_to_int(ip):
    parts = list(map(int, ip.split('.')))
    return (parts[0]<<24)|(parts[1]<<16)|(parts[2]<<8)|parts[3]

# trie = IPTrie()
# trie.insert(ip_to_int("192.168.1.0"), 24, "LAN")
# trie.insert(ip_to_int("192.168.0.0"), 16, "WAN")
# trie.lookup(ip_to_int("192.168.1.5")) → "LAN"

def union_length(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # interval opens
        events.append((end, -1))    # interval closes
    events.sort()
    total_length = 0
    active = 0
    prev_x = None
    for x, typ in events:
        if active > 0 and prev_x is not None:
            total_length += x - prev_x
        active += typ
        prev_x = x
    return total_length

# Total covered length
# union_length([(1,5),(2,7),(9,12)]) → 9
# Union: [1,7] ∪ [9,12] = 6 + 3 = 9

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, l_inv = count_inversions(arr[:mid])
    right, r_inv = count_inversions(arr[mid:])
    merged, split_inv = merge_count(left, right)
    return merged, l_inv + r_inv + split_inv

def merge_count(left, right):
    result = []
    inversions = 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            inversions += len(left) - i
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, inversions

# DFS approach
def find_provinces_dfs(isConnected):
    n = len(isConnected)
    visited = [False] * n
    provinces = 0
    def dfs(i):
        visited[i] = True
        for j in range(n):
            if isConnected[i][j] and not visited[j]:
                dfs(j)
    for i in range(n):
        if not visited[i]:
            dfs(i)
            provinces += 1
    return provinces

# Union-Find approach
def find_provinces_uf(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        pa, pb = find(a), find(b)
        if pa != pb:
            parent[pa] = pb
    for i in range(n):
        for j in range(i+1, n):
            if isConnected[i][j]:
                union(i, j)
    return len(set(find(i) for i in range(n)))

# find_provinces_dfs([[1,1,0],[1,1,0],[0,0,1]]) → 2

def delete_node(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Find inorder successor (smallest in right subtree)
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete_node(root.right, succ.val)
    return root

class NumMatrix:
    def __init__(self, matrix):
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                self.prefix[i][j] = (matrix[i-1][j-1]
                    + self.prefix[i-1][j]
                    + self.prefix[i][j-1]
                    - self.prefix[i-1][j-1])

    def sum_region(self, r1, c1, r2, c2):
        return (self.prefix[r2+1][c2+1]
                - self.prefix[r1][c2+1]
                - self.prefix[r2+1][c1]
                + self.prefix[r1][c1])

# matrix = [[3,0,1,4,2],[5,6,3,2,1],
#           [1,2,0,1,5],[4,1,0,1,7]]
# nm = NumMatrix(matrix)
# nm.sum_region(2, 1, 4, 3) → error (use valid range)
# nm.sum_region(1, 1, 2, 2) → 6+3+2+0 = 11

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

def reverse_list_rec(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

def longest_k_distinct(s, k):
    freq = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

# longest_k_distinct("eceba", 2) → 3 ("ece")
# longest_k_distinct("aa", 1) → 2

class Codec:
    def encode(self, strs):
        return ''.join(f'{len(s)}#{s}' for s in strs)

    def decode(self, s):
        result = []
        i = 0
        while i < len(s):
            j = s.index('#', i)
            length = int(s[i:j])
            result.append(s[j+1:j+1+length])
            i = j + 1 + length
        return result

# encode(["hello","world"]) → "5#hello5#world"