# — Arithmetic —
max(3, 7)                              # 7
min(3, 7)                              # 3
abs(-5)                                # 5  (no overflow trap unlike Java)

# — Power & Root —
2 ** 10                                # 1024  (exact int)
pow(2, 10)                             # 1024  (same)
pow(2, 10, 1000)                       # 24    (modular: 1024 % 1000)
math.sqrt(49)                          # 7.0   (float)
math.isqrt(49)                         # 7     (exact int, 3.8+)
int(math.sqrt(49))                     # 7

# Perfect square check (use isqrt for precision)
sq = math.isqrt(n)
is_perfect = sq * sq == n

# — Rounding —
math.floor(2.7)                        # 2
math.ceil(2.1)                         # 3
round(2.5)                             # 2  ← banker's rounding (rounds to even!)
round(3.5)                             # 4
int(2.7)                               # 2  (truncates toward zero)
int(-2.7)                              # -2

# — Logarithms —
math.log(math.e)                       # 1.0  (natural log)
math.log2(8)                           # 3.0
math.log10(1000)                       # 3.0

# Number of digits in n (n must be > 0; log10(0) raises ValueError!)
digits = len(str(n))                   # simplest, works for any n
digits = math.floor(math.log10(n)) + 1 # math-based, n > 0 only

# — Integer division & modulo —
7 // 2                                 # 3   (floor division)
-7 // 2                                # -4  (floors toward −∞, NOT truncate!)
-7 % 3                                 # 2   (sign of divisor, unlike C/Java)

# — Ceiling division (positive a, b) —
ceil_div = (a + b - 1) // b            # or -(-a // b)

# — Safe infinity for DP / shortest path —
INF = float('inf')                     # safe for comparisons, no overflow
INF + 1                                # still inf
INF > 10**18                           # True

# GCD — built-in (3.5+)
math.gcd(12, 8)                        # 4
math.gcd(12, 8, 6)                     # 2  (multi-arg, 3.9+)

# LCM — built-in (3.9+)
math.lcm(4, 6)                         # 12
math.lcm(4, 6, 10)                     # 60  (multi-arg)

# LCM for < 3.9
def lcm(a, b): return a // math.gcd(a, b) * b

# isPrime — trial division O(√n)
def is_prime(n):
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0 or n % 3 == 0: return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0: return False
        i += 6
    return True

# Modular exponentiation O(log exp) — built-in!
MOD = 1_000_000_007
pow(base, exp, MOD)                    # built-in 3-arg pow

# Safe modular add
(a % MOD + b % MOD) % MOD

# Safe modular multiply (no overflow in Python!)
a * b % MOD

# 1D DP with infinity
dp = [float('inf')] * n
dp[0] = 0  # base case

# 2D DP with infinity
dp = [[float('inf')] * cols for _ in range(rows)]

# Memoization (sentinel = -1 for uncomputed)
memo = [-1] * n

# Boolean DP
dp = [False] * (n + 1)
dp[0] = True  # base: empty subset

# Space-optimized (two variables) — House Robber pattern
prev2, prev1 = 0, 0
for num in nums:
    curr = max(prev1, prev2 + num)
    prev2 = prev1
    prev1 = curr

# @lru_cache for recursive memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(i, j):
    if i >= n: return 0
    return max(solve(i + 1, j), solve(i + 1, j - 1) + val[i])

# ❌ // floors toward -∞, NOT toward zero like C/Java
-7 // 2                                # -4 (not -3!)
-1 // 2                                # -1 (not 0!)

# ✅ Truncation toward zero (C/Java behavior)
int(-7 / 2)                            # -3
math.trunc(-7 / 2)                     # -3

# ❌ % follows floor division — sign of divisor
-7 % 3                                 # 2  (not -1 like C/Java!)

# This actually helps: Python modulo is always non-negative
# when divisor is positive — no ((a % n) + n) % n needed

# ❌ round() rounds to nearest EVEN for .5 (banker's rounding)
round(0.5)                             # 0  (not 1!)
round(1.5)                             # 2  (rounds to nearest even)
round(2.5)                             # 2  (not 3!)

# ✅ For always-round-up: math.floor(x + 0.5)
# ✅ For ceiling: math.ceil(x)

# ❌ Float comparison fails due to IEEE 754
0.1 + 0.2 == 0.3                       # False!
0.1 + 0.2                              # 0.30000000000000004

# ✅ Use math.isclose() or epsilon
math.isclose(0.1 + 0.2, 0.3)          # True
abs(a - b) < 1e-9                      # manual epsilon

# float('inf') is safe for comparisons but has edge cases
float('inf') - float('inf')           # nan (not 0!)
float('inf') * 0                       # nan
float('inf') == float('inf')           # True
float('nan') == float('nan')           # False! (NaN != NaN)

# ✅ For DP/shortest path, float('inf') works cleanly:
if dist[u] + w < dist[v]:             # no overflow risk
    dist[v] = dist[u] + w

# — int ↔ str —
str(42)                                # "42"
int("42")                              # 42
float("3.14")                          # 3.14
f"{42:05d}"                            # "00042"  (formatted)

# — char ↔ int (alphabet index) —
ord('c') - ord('a')                    # 2
ord('7') - ord('0')                    # 7
chr(ord('a') + 2)                      # 'c'
ord('A')                               # 65

# — Radix conversions —
bin(10)                                # "0b1010"
hex(255)                               # "0xff"
oct(8)                                 # "0o10"
int("1010", 2)                         # 10
int("ff", 16)                          # 255
int("10", 8)                           # 8
f"{10:b}"                              # "1010" (no prefix)
f"{255:x}"                             # "ff"   (no prefix)

# — str ↔ list of chars —
list("hello")                          # ['h', 'e', 'l', 'l', 'o']
"".join(['h', 'i'])                    # "hi"

# — Boolean —
bool(0)                                # False
bool("")                               # False
bool([])                               # False
bool(None)                             # False
bool(1)                                # True  (any non-zero)
bool("hi")                             # True  (any non-empty)

# int() on float truncates toward zero (like C), not floor
int(2.9)                               # 2  (not 3)
int(-2.9)                              # -2 (not -3)
int(-0.5)                              # 0

# ✅ Use math.floor / math.ceil for directional rounding
math.floor(-2.9)                       # -3
math.ceil(-2.9)                        # -2

# ⚠ int("3.14") raises ValueError — must use float() first
int(float("3.14"))                     # 3

'7'.isdigit()                          # True
'A'.isalpha()                          # True
'3'.isalnum()                          # True
' '.isspace()                          # True
'A'.isupper()                          # True
'a'.islower()                          # True

# Inline ASCII checks (tight loops):
'a' <= c <= 'z'                       # lowercase
'A' <= c <= 'Z'                       # uppercase
'0' <= c <= '9'                       # digit

c.upper()                              # 'a' → 'A'
c.lower()                              # 'A' → 'a'

# Bit-level case tricks (ASCII letters only):
chr(ord(c) | 32)                       # force lowercase
chr(ord(c) & 95)                       # force uppercase
chr(ord(c) ^ 32)                       # toggle case

# Vowel check
c.lower() in 'aeiou'                   # pythonic
c.lower() in {'a', 'e', 'i', 'o', 'u'} # O(1) set lookup

# — Single-bit operations —
(n >> i) & 1                           # check bit i
n | (1 << i)                           # set bit i
n & ~(1 << i)                          # clear bit i
n ^ (1 << i)                           # toggle bit i

# — Lowest set bit, Kernighan's —
n & (-n)                               # isolate rightmost 1: 12(1100) → 4(0100)
n & (n - 1)                            # clear lowest set bit

# Count set bits
bin(n).count('1')                      # any version
n.bit_count()                          # 3.10+

# — Shifts, even/odd —
n << k                                 # n × 2^k
n >> k                                 # n ÷ 2^k (arithmetic, floors)
n & 1 == 0                             # even
n & 1 == 1                             # odd

# — XOR rules —
a ^ 0 == a                             # unchanged
a ^ a == 0                             # self-cancels ← key for Single Number
a ^ b ^ a == b                         # associative + self-cancel

# — Swap without temp —
a, b = b, a                            # Pythonic swap (no XOR trick needed)

# — Bitmask & subset enumeration —
(1 << n) - 1                           # n=4 → 0b1111 = 15

sub = mask
while sub > 0:
    # process sub
    sub = (sub - 1) & mask
# don't forget empty subset (sub = 0)

# — 32-bit mask (for LeetCode problems expecting 32-bit) —
n & 0xFFFFFFFF                         # simulate unsigned 32-bit

# ❌ Common mistake: ^ is XOR in Python, not exponentiation
2 ^ 3                                  # 1  (XOR: 10 ^ 11 = 01)

# ✅ Use ** for power
2 ** 3                                 # 8

# Python ints have infinite precision — ~0 is -1, not 0xFFFFFFFF
~0                                     # -1
~5                                     # -6  (-(5+1))
bin(-5)                                # '-0b101'  (shows negative sign)

# For 32-bit problems (e.g. LeetCode Reverse Bits):
# ✅ Mask with 0xFFFFFFFF to simulate 32-bit unsigned
n = -1
n & 0xFFFFFFFF                         # 4294967295 (0xFFFFFFFF)

# Empty list
arr = []
arr = list()

# Pre-filled
arr = [0] * n                          # [0, 0, ..., 0]
arr = [1, 2, 3]

# List comprehension
arr = [i * 2 for i in range(5)]        # [0, 2, 4, 6, 8]
arr = [0 for _ in range(n)]            # same as [0] * n

# 2D list
grid = [[0] * cols for _ in range(rows)]

# ❌ 2D trap: shared reference
grid = [[0] * cols] * rows             # all rows point to SAME list!

# From string / iterable
list("hello")                          # ['h', 'e', 'l', 'l', 'o']
list(range(5))                         # [0, 1, 2, 3, 4]

# — Sort —
arr.sort()                             # ascending, in-place
arr.sort(reverse=True)                 # descending
sorted(arr)                            # returns new sorted list

# Sort 2D by first element
intervals.sort(key=lambda x: x[0])

# Sort by multiple keys
intervals.sort(key=lambda x: (x[0], -x[1]))  # asc by [0], desc by [1]

# Sort by string length
words.sort(key=len)

# — Copy —
cp = arr[:]                            # shallow copy
cp = arr.copy()                        # same
cp = list(arr)                         # same

# 2D deep copy
import copy
cp2d = copy.deepcopy(grid)
# or manually:
cp2d = [row[:] for row in grid]

# — Aggregate —
sum(arr)                               # total
min(arr)                               # minimum
max(arr)                               # maximum

# — Reverse in-place —
arr.reverse()
arr[::-1]                              # reversed copy

# — Shuffle —
import random
random.shuffle(arr)                    # in-place

# — Remove at index —
arr.pop(i)                             # O(n), returns removed element
del arr[i]                             # O(n), no return

# — Rotate left by k —
k %= len(arr)
arr = arr[k:] + arr[:k]

# — Remove duplicates (preserve order) —
arr = list(dict.fromkeys(arr))

# — Remove duplicates (sorted) —
arr = sorted(set(arr))

# — Flatten 2D —
flat = [x for row in grid for x in row]

# — Zip —
list(zip([1, 2], ['a', 'b']))          # [(1, 'a'), (2, 'b')]
list(zip(*matrix))                     # transpose

# — Enumerate —
for i, val in enumerate(arr):          # index + value
    pass

# — Print —
print(arr)                             # [1, 2, 3]

# ❌ All rows point to the SAME inner list
grid = [[0] * 3] * 3
grid[0][0] = 1
print(grid)                            # [[1,0,0], [1,0,0], [1,0,0]]  all changed!

# ✅ Use list comprehension — each row is independent
grid = [[0] * 3 for _ in range(3)]
grid[0][0] = 1
print(grid)                            # [[1,0,0], [0,0,0], [0,0,0]]  correct

# ✅ Guard before any logic
if not nums: return ...
if len(nums) < 2: return nums[0]

# Kadane's: init with nums[0], loop from i=1 → needs guard
# Two pointers: right = len(nums)-1 → -1 if empty
# Fixed window: k > n → index out of range

# — Access —
len(s)                                 # length
s[i]                                   # char at index
s[i:j]                                 # substring [i, j)
s[-1]                                  # last char
s[::-1]                                # reversed string

# — Search —
s.find("sub")                          # first index, -1 if not found
s.rfind("sub")                         # last index, -1 if not found
s.index("sub")                         # first index, raises ValueError
"sub" in s                             # boolean
s.startswith("pre")                    # starts with
s.endswith("suf")                      # ends with
s.count("a")                           # count occurrences

# — Transform —
s.lower()                              # lowercase
s.upper()                              # uppercase
s.strip()                              # trim whitespace both ends
s.lstrip()                             # trim left
s.rstrip()                             # trim right
s.replace("old", "new")               # replace all
s.replace("old", "new", 1)            # replace first only
s.split(",")                           # split by separator
s.split()                              # split by any whitespace
",".join(["a", "b", "c"])             # "a,b,c"
"ab" * 3                               # "ababab"

# — Mutate via list —
chars = list(s)
chars[0] = 'X'
s = "".join(chars)

# — Reverse (via slicing) —
s[::-1]                                # "hello" → "olleh"

# — Anagram key —
key = "".join(sorted(s))               # sorted chars
key = tuple(sorted(s))                 # tuple key for dict

# Frequency array key (no sort needed)
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
key = tuple(freq)                      # hashable key for dict

# — Regex —
import re
re.findall(r'\d+', "a1b2c3")          # ['1', '2', '3']
re.match(r'^[a-z]+$', s)              # match from start
re.sub(r'\s+', ' ', s)                # replace multiple spaces

# ❌ O(n²) — each += creates a new string
result = ""
for c in chars:
    result += c                        # quadratic!

# ✅ O(n) — build list, join at end
parts = []
for c in chars:
    parts.append(c)
result = "".join(parts)

# ✅ Or use list comprehension
result = "".join(c for c in chars)

# ⚠ Completely different behavior!
"".split()                             # []      (empty list)
"".split(",")                          # [""]    (list with one empty string!)

# "a,,b".split(",") returns ["a", "", "b"] — empties between delims
# "a  b".split()    returns ["a", "b"]  — no empties (collapses whitespace)

# Empty string → palindrome (True)
# Single char → palindrome (True)

# Valid Palindrome: strip non-alphanumeric, lowercase
def is_palindrome(s):
    clean = [c.lower() for c in s if c.isalnum()]
    return clean == clean[::-1]

# Two-pointer (no extra space):
def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum(): l += 1
        while l < r and not s[r].isalnum(): r -= 1
        if s[l].lower() != s[r].lower(): return False
        l += 1; r -= 1
    return True

# Sort ascending
arr.sort()                             # in-place
sorted(arr)                            # new list

# Sort descending
arr.sort(reverse=True)
sorted(arr, reverse=True)

# Sort by key function
arr.sort(key=lambda x: x[0])          # by first element
arr.sort(key=abs)                      # by absolute value
arr.sort(key=len)                      # by length

# Multi-key sort: asc by start, desc by end
intervals.sort(key=lambda x: (x[0], -x[1]))

# Largest Number #179 — concat comparison
from functools import cmp_to_key
strs.sort(key=cmp_to_key(lambda a, b: (b+a > a+b) - (b+a < a+b)))

# Stable sort — TimSort is always stable
# Equal elements preserve their original order

# Check if sorted
all(arr[i] <= arr[i+1] for i in range(len(arr)-1))

# Sort dict by value
sorted(d.items(), key=lambda x: x[1])

# Sort with None handling
arr.sort(key=lambda x: (x is None, x))  # None goes last

# Next permutation (no built-in, implement manually)
# Or use itertools.permutations for all permutations

# ✅ key= for simple transformations (preferred)
arr.sort(key=lambda x: -x)            # descending
arr.sort(key=lambda x: (x[0], -x[1])) # multi-key

# ✅ cmp_to_key when comparison is pairwise (e.g. concatenation)
from functools import cmp_to_key
def compare(a, b):
    if a + b > b + a: return -1        # a should come first
    elif a + b < b + a: return 1
    return 0
strs.sort(key=cmp_to_key(compare))

# ⚠ cmp_to_key is slower — prefer key= when possible

import bisect

# Binary search (sorted list)
idx = bisect.bisect_left(sorted_arr, target)
found = idx < len(sorted_arr) and sorted_arr[idx] == target

# Lower / upper bound
lb = bisect.bisect_left(arr, target)   # first index where arr[i] >= target
ub = bisect.bisect_right(arr, target)  # first index where arr[i] > target
count = ub - lb                        # number of occurrences of target

# Find minimum in rotated sorted array
def find_min(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 lo

# Search in rotated array
def search(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]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else: lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else: hi = mid - 1
    return -1

# ❌ No progress when lo=0, hi=1: mid=0, lo stays 0
while lo < hi:
    mid = (lo + hi) // 2
    if valid(mid): hi = mid
    else: lo = mid                     # INFINITE LOOP!

# ✅ Always advance by at least 1
    else: lo = mid + 1

# Rule: lo < hi  → boundary-finding
# Rule: lo <= hi → exact-match

# lo/hi must cover the complete valid range!

# Koko Eating Bananas:
lo = 1                                 # minimum possible rate
hi = max(piles)                        # one pile per hour

# Capacity to Ship:
lo = max(weights)                      # must fit heaviest package
hi = sum(weights)                      # ship everything in one day

# is_feasible must be strictly monotone!

# — Dict operations —
d = {}
d[key] = val                           # put
val = d[key]                           # get (KeyError if missing)
val = d.get(key, 0)                    # get with default
del d[key]                             # remove
key in d                               # contains
len(d)                                 # size

# Frequency counting
freq = {}
for n in nums: freq[n] = freq.get(n, 0) + 1

# — defaultdict (auto-creates missing keys) —
from collections import defaultdict
freq = defaultdict(int)
for n in nums: freq[n] += 1           # no KeyError

groups = defaultdict(list)
for key, item in items: groups[key].append(item)

# — Counter (frequency Swiss army knife) —
from collections import Counter
freq = Counter(nums)                   # {1: 3, 2: 2, ...}
freq.most_common(k)                    # top-k [(val, count), ...]
freq[missing_key]                      # 0 (no KeyError)
freq1 == freq2                         # True if same frequencies

# Decrement and remove if zero
freq[key] -= 1
if freq[key] == 0: del freq[key]

# — Set operations —
s = set()
s = {1, 2, 3}
s.add(x)                              # add
s.discard(x)                          # remove (no error)
x in s                                 # contains
s1 | s2                                # union
s1 & s2                                # intersection
s1 - s2                                # difference
s1 ^ s2                                # symmetric difference

# Set from list
s = set(arr)

# Visited pattern (BFS/DFS)
visited = set()
if node not in visited:
    visited.add(node)

# — Ordered iteration (dict is insertion-ordered 3.7+) —
for k, v in d.items(): pass            # insertion order
for k in sorted(d): pass               # sorted keys

# — frozenset (hashable set, usable as dict key) —
fs = frozenset([1, 2, 3])
d[fs] = "value"                        # frozenset as key

# ❌ Default list/dict is shared across all calls
def add(val, lst=[]):
    lst.append(val)
    return lst
add(1)                                 # [1]
add(2)                                 # [1, 2]  — NOT [2]!

# ✅ Use None as sentinel
def add(val, lst=None):
    if lst is None: lst = []
    lst.append(val)
    return lst

import heapq

# — Min-heap —
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 3)
heapq.heappush(h, 7)
top = heapq.heappop(h)                # 3 (smallest)
peek = h[0]                            # peek without removing

# Heapify existing list
arr = [5, 3, 7, 1]
heapq.heapify(arr)                     # O(n), arr is now a valid heap

# — Max-heap (negate values) —
heapq.heappush(h, -val)               # push negated
top = -heapq.heappop(h)               # pop and negate back

# — Tuple heap (multi-key, compared element-by-element) —
# Dijkstra: (distance, node)
heapq.heappush(h, (dist, node))
d, u = heapq.heappop(h)

# Frequency-based: (-freq, val) for max-freq first
for val, cnt in freq.items():
    heapq.heappush(h, (-cnt, val))

# — Top-K via heap —
h = []
for v in data:
    heapq.heappush(h, v)
    if len(h) > k:
        heapq.heappop(h)              # evict smallest
# h now holds the k largest elements

# — Merge sorted lists —
merged = list(heapq.merge(sorted1, sorted2))

# ❌ heapq is ALWAYS min-heap
heapq.heappush(h, val)
top = heapq.heappop(h)                # returns SMALLEST

# ✅ Negate for max-heap
heapq.heappush(h, -val)
top = -heapq.heappop(h)               # returns LARGEST

# ⚠ With tuples: negate the priority, not the value
heapq.heappush(h, (-priority, value))
p, v = heapq.heappop(h)
actual_priority = -p

from collections import deque

# — Stack via list —
stack = []
stack.append(x)                        # push
top = stack[-1]                        # peek
stack.pop()                            # pop
not stack                              # isEmpty

# — Queue via deque (NOT list.pop(0)!) —
queue = deque()
queue.append(x)                        # enqueue
front = queue[0]                       # peek
queue.popleft()                        # dequeue O(1)
not queue                              # isEmpty

# — Deque —
dq = deque()
dq.append(x)                          # push back
dq.appendleft(x)                      # push front
dq.pop()                              # pop back
dq.popleft()                          # pop front
dq[0]                                  # peek front
dq[-1]                                 # peek back

# Deque with max length (auto-evicts from opposite end)
dq = deque(maxlen=k)

# — Sliding window maximum (monotonic decreasing deque) —
dq = deque()                           # stores indices
result = []
for i, num in enumerate(nums):
    while dq and nums[dq[-1]] < num:
        dq.pop()                       # remove smaller from back
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()                   # out of window
    if i >= k - 1:
        result.append(nums[dq[0]])

from collections import OrderedDict

# LRU cache via OrderedDict
class LRU:
    def __init__(self, cap):
        self.cap = cap
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)    # mark as recently used
        return self.cache[key]

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

# Or use @functools.lru_cache for function memoization

# ❌ O(n) per dequeue — shifts all elements
queue = []
queue.append(x)
queue.pop(0)                           # O(n)!

# ✅ O(1) per dequeue
from collections import deque
queue = deque()
queue.append(x)
queue.popleft()                        # O(1)

# ❌ IndexError on empty
stack[-1]                              # IndexError
stack.pop()                            # IndexError
deque().popleft()                      # IndexError

# ✅ Always check before accessing
if stack: top = stack[-1]
if queue: front = queue[0]

# 4-directional (up, right, down, left)
DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# 8-directional (includes diagonals)
DIRS8 = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

# Bounds check
def in_bounds(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

for dr, dc in DIRS:
    nr, nc = r + dr, c + dc
    if in_bounds(nr, nc, rows, cols):
        pass  # valid neighbor

# 2D ↔ 1D index
idx = r * cols + c
r, c = divmod(idx, cols)

# Transpose
list(zip(*matrix))                     # returns list of tuples
[[row[i] for row in matrix] for i in range(len(matrix[0]))]

# Rotate 90° clockwise = transpose + reverse each row
rotated = [list(row)[::-1] for row in zip(*matrix)]

# Spiral traversal: 4 boundaries shrinking
top, bot, left, right = 0, m - 1, 0, n - 1
while top <= bot and left <= right:
    # → top row, ↓ right col, ← bottom row, ↑ left col
    top += 1; right -= 1; bot -= 1; left += 1

# Diagonal properties:
# Same diagonal:      r - c  is constant
# Same anti-diagonal: r + c  is constant

# Grid DFS (4-directional)
def dfs(grid, vis, r, c):
    if not in_bounds(r, c, len(grid), len(grid[0])) or vis[r][c]:
        return
    vis[r][c] = True
    for dr, dc in DIRS:
        dfs(grid, vis, r + dr, c + dc)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

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

# Adjacency list — unweighted undirected
from collections import defaultdict
adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)                   # omit for directed

# Weighted: {neighbor: weight}
adj = defaultdict(list)
for u, v, w in edges:
    adj[u].append((v, w))

# In-degree array (for Kahn's topo sort)
in_deg = [0] * n
for u, v in edges: in_deg[v] += 1

# Union-Find (DSU) with path compression + union by rank
parent = list(range(n))
rank = [0] * n

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

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

if not head: return None
if not head.next: return head

# Iterate safely
while curr:
    curr = curr.next

# Dummy head avoids None checks for head insertion/deletion
dummy = ListNode(0, head)
# ... work with dummy ...
return dummy.next

# ✅ Short-circuit: fast checked before fast.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# ✅ Reverse: save next before overwriting
nxt = curr.next                        # 1. save
curr.next = prev                       # 2. reverse
prev = curr                            # 3. advance prev
curr = nxt                             # 4. advance curr

# Floyd's cycle: phase 2 — find cycle start
ptr = head
while ptr != slow:
    ptr = ptr.next
    slow = slow.next
return ptr                             # cycle entry point

# DFS base case — always first line
if not node: return 0

# BFS start
if not root: return result

# BST validate — use float('inf') bounds (no overflow in Python!)
def validate(n, lo, hi):
    if not n: return True
    if n.val <= lo or n.val >= hi: return False
    return validate(n.left, lo, n.val) and validate(n.right, n.val, hi)
validate(root, float('-inf'), float('inf'))

# Max Path Sum: init to -inf (not 0!)
ans = float('-inf')

# Skewed tree (n=10^5 all left): use iterative to avoid stack overflow
# Python default recursion limit is 1000!
import sys
sys.setrecursionlimit(200000)          # increase for deep recursion

# ❌ Only visits component containing node 0
dfs(graph, 0, visited)
# ✅ Start from every unvisited node
for i in range(n):
    if i not in visited:
        dfs(graph, i, visited)
        components += 1

# Dijkstra: must skip stale entries
d, u = heapq.heappop(h)
if d > dist[u]: continue

# Dijkstra: unreachable nodes
if dist[dst] == float('inf'): return -1
# ❌ Dijkstra with negative weights → use Bellman-Ford

# Undirected DFS: ignore parent, not all visited neighbors
if neighbor == parent: continue
if neighbor in visited: return True    # real cycle
# For directed: use 3-state (unvisited / in-stack / done)

# ❌ Python default recursion limit is 1000
# Deep DFS on n=100000 nodes → RecursionError!

# ✅ Increase limit
import sys
sys.setrecursionlimit(300000)

# ✅ Or convert to iterative with explicit stack
stack = [root]
while stack:
    node = stack.pop()
    if node.right: stack.append(node.right)
    if node.left: stack.append(node.left)

# — String palindrome (two pointers) —
l, r = 0, len(s) - 1
while l < r:
    if s[l] != s[r]: return False
    l += 1; r -= 1

# — Integer palindrome (no string conversion) —
if x < 0 or (x % 10 == 0 and x != 0): return False
rev = 0
while x > rev:
    rev = rev * 10 + x % 10
    x //= 10
return x == rev or x == rev // 10

# — Expand around center (longest palindrome) —
def expand(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1; r += 1
    return r - l - 1

# — Find minimum / maximum —
ans = float('inf')
ans = min(ans, candidate)

# — Collect results: always copy the list! —
result.append(current[:])             # shallow copy via slicing
result.append(list(current))          # or list() constructor

# — Frequency arrays —
freq = [0] * 26                        # 26 lowercase letters
for c in s: freq[ord(c) - ord('a')] += 1

# Or use Counter
from collections import Counter
freq = Counter(s)

# — Early-return checklist —
if not nums: return ...                # empty list
if not s: return ...                   # empty string
if not root: return ...                # None tree
if not head: return head               # None linked list
if k > len(nums): return 0             # window too large

if k > len(nums): return 0
if len(p) > len(s): return False       # Permutation In String

# Matches counter — increment only at exact boundary
if window[c] == need[c]: formed += 1

# Decrement only when crossing below threshold
window[lc] -= 1
if window[lc] < need[lc]: formed -= 1

# Climbing Stairs: n=1 → dp[i-2] accesses dp[-1] (valid in Python, but wrong!)
if n <= 1: return n

# Decode Ways: s[0]='0' → 0 ways immediately
# Coin Change: amount=0 → 0 (no coins needed)
# Edit Distance: dp[i][0]=i, dp[0][j]=j → don't forget!

# House Robber II: can't use first and last together
if len(nums) == 1: return nums[0]
return max(rob(nums[:-1]), rob(nums[1:]))

# Unbounded (Coin Change): each coin reusable → loop FORWARD
for coin in coins:
    for j in range(coin, amount + 1):
        dp[j] = min(dp[j], dp[j - coin] + 1)

# 0/1 Knapsack: each item once → loop BACKWARD
for w, v in items:
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)

# ❌ All results point to the SAME list object
result.append(current)
# ✅ Always copy on add
result.append(current[:])              # slice copy
result.append(list(current))           # list copy

# ❌ i > 0: skips valid combinations (too aggressive)
if i > 0 and nums[i] == nums[i - 1]: continue
# ✅ i > start: only skip duplicates at same recursion level
if i > start and nums[i] == nums[i - 1]: continue
# MUST sort array first!
nums.sort()

# Kadane's: ❌ init max_so_far = 0 → [-3,-1,-2] wrongly returns 0
# ✅ Init from first element
max_so_far = curr = nums[0]

# Max Product [2,3,0,4]: zero resets the subarray
# Product Except Self with zero: 2+ zeros → all products are zero

# 3Sum [0,0,0] → duplicate skip avoids repeated i starts, not valid triples
# if i > 0 and nums[i] == nums[i-1]: continue

# Longest Consecutive [1,1,1] → answer=1 (not 3); use set

# Rotated Sorted Array II [1,1,1,1]: can't determine sorted half
if nums[lo] == nums[mid] == nums[hi]:
    lo += 1; hi -= 1                   # linear fallback

# Subarray length: right - left + 1
# Substring s[i:j]: [i, j), length = j - i

# for l < r  vs  for l <= r
# Binary search: lo <= hi for exact-match
# Binary search: lo < hi  for boundary-finding

# Return conventions:
# Binary Search not found    → -1
# Coin Change impossible     → -1 (NOT 0!)
# Min Window no window       → ""
# Subsets: empty set []      → valid result

# ⚠ Python negative indexing: s[-1] is valid (last char)
# This means s[right] with right=-1 does NOT crash —
# it silently returns the wrong element!

import itertools
from functools import lru_cache, cmp_to_key

# — Combinatorics —
itertools.permutations([1,2,3])        # all 3! = 6 permutations
itertools.permutations([1,2,3], 2)     # 2-length permutations (P(3,2) = 6)
itertools.combinations([1,2,3], 2)     # C(3,2) = 3: (1,2),(1,3),(2,3)
itertools.combinations_with_replacement([1,2], 2)  # (1,1),(1,2),(2,2)
itertools.product([0,1], repeat=3)     # all 2^3 = 8 binary strings

# — Iterators —
itertools.chain([1,2], [3,4])          # 1, 2, 3, 4  (flatten)
itertools.accumulate([1,2,3,4])        # 1, 3, 6, 10 (prefix sums)
itertools.groupby(sorted(data), key=lambda x: x[0])  # group by first element
itertools.zip_longest([1,2], [3])      # (1,3), (2,None)

# — Memoization —
@lru_cache(maxsize=None)
def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

# ⚠ lru_cache only works with hashable arguments
# Lists → convert to tuple first
# Clear cache: fib.cache_clear()

# — Prefix sums via accumulate —
from itertools import accumulate
prefix = list(accumulate(nums))        # [a, a+b, a+b+c, ...]
prefix = [0] + list(accumulate(nums))  # 0-indexed prefix sum

# — Enumerate from 1 —
for i, val in enumerate(arr, 1): pass  # i starts at 1

# — Print —
print("hello", 42)                     # hello 42
print(f"name={name} age={age}")        # f-string (3.6+)
print(f"{3.14159:.2f}")                # "3.14"
print(*arr, sep=", ")                  # 1, 2, 3
print(arr)                             # [1, 2, 3]
print("no newline", end="")            # suppress newline

# — Input —
s = input()                            # read line (str)
n = int(input())                       # read int
a, b = map(int, input().split())       # read two ints
arr = list(map(int, input().split()))  # read int array

# Fast input for competitive programming
import sys
input = sys.stdin.readline             # much faster

# — File I/O —
with open("file.txt") as f:
    data = f.read()                    # entire file as string
    lines = data.splitlines()          # list of lines (from already-read data)

with open("file.txt", "w") as f:
    f.write("hello\n")

# — String formatting —
f"{42:05d}"                            # "00042"  (zero-padded)
f"{255:08b}"                           # "11111111" (binary, 8-wide)
f"{255:#x}"                            # "0xff"   (hex with prefix)
f"{3.14:.4f}"                          # "3.1400" (4 decimal places)