Run Detail

def is_leap(year: int) -> bool:
    return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)

def is_leap(year: int) -> bool:
    return year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)

def is_leap(year: int) -> bool:
    return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

def rle(s: str) -> str:
    if not s:
        return ""
    result = []
    count = 1
    curr = s[0]
    for char in s[1:]:
        if char == curr:
            count += 1
        else:
            result.append(f"{curr}{count}")
            curr = char
            count = 1
    result.append(f"{curr}{count}")
    return "".join(result)

def rle(s: str) -> str:
    if not s:
        return ""
    result = []
    i = 0
    n = len(s)
    while i < n:
        char = s[i]
        count = 1
        while i + count < n and s[i + count] == char:
            count += 1
        result.append(f"{char}{count}")
        i += count
    return "".join(result)

def rle(s: str) -> str:
    if not s:
        return ""
    result = []
    current_char = s[0]
    count = 1
    for i in range(1, len(s)):
        char = s[i]
        if char == current_char:
            count += 1
        else:
            result.append(f"{current_char}{count}")
            current_char = char
            count = 1
    result.append(f"{current_char}{count}")
    return "".join(result)

def chunks(items, n: int) -> list[list]:
    if n < 1:
        raise ValueError("n must be at least 1")
    result = []
    current = []
    for item in items:
        current.append(item)
        if len(current) == n:
            result.append(current)
            current = []
    if current:
        result.append(current)
    return result

from itertools import islice

def chunks(items, n: int) -> list[list]:
    if n < 1:
        raise ValueError("n must be at least 1")
    result = []
    iterator = iter(items)
    while True:
        chunk = list(islice(iterator, n))
        if not chunk:
            break
        result.append(chunk)
    return result

from itertools import islice

def chunks(items, n: int) -> list[list]:
    if n < 1:
        raise ValueError("n must be >= 1")
    it = iter(items)
    result = []
    while True:
        chunk = list(islice(it, n))
        if not chunk:
            break
        result.append(chunk)
    return result

def round_half_up(value: str, digits: int) -> str:
    negative = value[0] == '-'
    value = value.lstrip('-')
    
    if '.' not in value:
        integer_part = value
        decimal_part = ''
    else:
        integer_part, decimal_part = value.split('.', 1)
    
    # Pad or truncate decimal part
    if len(decimal_part) > digits:
        decimal_part = decimal_part[:digits + 1]
    else:
        decimal_part = decimal_part.zfill(digits + 1)
    
    # Get the digit at rounding position and the next digit
    rounding_digit = int(decimal_part[digits])
    next_digit = int(decimal_part[digits + 1]) if digits + 1 < len(decimal_part) else 0
    
    # Check if it's an exact tie (digit is 5 and rest are 0)
    is_exact_tie = (rounding_digit == 5 and 
                   all(c == '0' for c in decimal_part[digits + 1:]))
    
    # Determine if we need to round up
    round_up = rounding_digit >= 5 or is_exact_tie
    
    if round_up:
        # Add 1 to the truncated decimal part
        truncated = decimal_part[:digits]
        carry = 1
        for i in range(digits - 1, -1, -1):
            truncated = truncated[:i] + str(int(truncated[i]) + 1)[0] + truncated[i+1:]
            if truncated[i] == '1':
                truncated = truncated[:i] + '0' + truncated[i+1:]
        # Handle carry to integer part
        if carry:
            carry = 1
            for i in range(digits - 1, -1, -1):
                truncated = truncated[:i] + str(int(truncated[i]) + 1)[0] + truncated[i+1:]
                if truncated[i] == '1':
                    truncated = truncated[:i] + '0' + truncated[i+1:]
            # Add carry to integer part
            integer_part = str(int(integer_part) + 1)
            truncated = truncated.zfill(digits)
    
    # Format result
    if digits == 0:
        result = integer_part
    else:
        result = f"{integer_part}.{truncated}"
    
    if negative:
        result = '-' + result
    
    return result

def round_half_up(value: str, digits: int) -> str:
    negative = value.startswith('-')
    value = value.lstrip('-')
    
    if '.' in value:
        int_part, frac_part = value.split('.')
    else:
        int_part = value
        frac_part = ''
    
    # Pad fractional part to have at least digits+1 characters
    if len(frac_part) < digits + 1:
        frac_part = frac_part.ljust(digits + 1, '0')
    else:
        frac_part = frac_part[:digits + 1]
    
    # Round digit at position digits, check next digit for exact tie
    round_digit = int(frac_part[digits])
    next_digit = int(frac_part[digits + 1]) if len(frac_part) > digits + 1 else 0
    
    # Determine if we need to round up (half up: round if >= 5)
    should_round_up = round_digit >= 5
    
    if should_round_up:
        # Truncate to digits
        frac_part = frac_part[:digits]
        # Add 1 to start of fractional part
        carry = 1
        for i in range(digits - 1, -1, -1):
            digit = int(frac_part[i]) + carry
            frac_part[i] = str(digit % 10)
            carry = digit // 10
        if carry:
            int_part = str(int(int_part) + 1)
    
    # Format result
    if digits == 0:
        result = int_part
    else:
        result = f"{int_part}.{frac_part}"
    
    if negative:
        result = '-' + result
    
    return result

def round_half_up(value: str, digits: int) -> str:
    if not value or not value.replace('.', '').replace('-', '').replace('+', '').isdigit():
        raise ValueError("Invalid number format")
    
    negative = value.startswith('-') or value.startswith('+')
    if negative:
        value = value[1:]
    
    if '.' not in value:
        integer_part = value
        decimal_part = ''
    else:
        integer_part, decimal_part = value.split('.', 1)
    
    # Ensure we have at least `digits` decimal places
    decimal_part = decimal_part.ljust(digits + 1, '0')
    
    # Extract rounding digit and remainder
    rounding_digit = int(decimal_part[digits - 1])
    remainder = decimal_part[digits:]
    
    # Check for exact tie: remainder is exactly "5" followed by only zeros or empty
    is_exact_tie = len(remainder) == 0 or (remainder[0] == '5' and all(c == '0' for c in remainder[1:]))
    
    # Round
    should_round_up = (is_exact_tie) or (int(remainder[0]) > 5 if len(remainder) > 1 else int(remainder[0]) >= 5)
    
    if should_round_up:
        carry = 1
        for i in range(digits - 1, -1, -1):
            d = int(decimal_part[i]) + carry
            decimal_part = decimal_part[:i] + str(d % 10) + decimal_part[i + 1:]
            carry = d // 10
        if carry:
            integer_part = str(int(integer_part) + 1)
    
    # Format result
    if digits == 0:
        result = integer_part
    else:
        result = integer_part + '.' + decimal_part[:digits]
    
    if negative:
        result = '-' + result
    
    return result

def parse_kv(line: str) -> dict[str, str]:
    if not line.strip():
        return {}
    
    result = {}
    tokens = line.split()
    
    for token in tokens:
        if '=' in token:
            key, value = token.split('=', 1)
            key = key.strip()
            if value.startswith('"') and value.endswith('"') and len(value) >= 2:
                value = value[1:-1]
            result[key] = value
    
    return result

def parse_kv(line: str) -> dict[str, str]:
    result = {}
    i = 0
    length = len(line)
    while i < length:
        # Skip leading whitespace
        while i < length and line[i].isspace():
            i += 1
        
        if i >= length:
            break
        
        # Find key (non-whitespace)
        key_start = i
        while i < length and not line[i].isspace():
            i += 1
        key = line[key_start:i]
        
        # Skip whitespace before '='
        while i < length and line[i].isspace():
            i += 1
        
        if i >= length or line[i] != '=':
            break
        
        # Consume '='
        i += 1
        
        # Skip whitespace after '='
        while i < length and line[i].isspace():
            i += 1
            
        # Parse value
        if i >= length:
            value = ""
        elif line[i] == '"':
            # Quoted value
            i += 1
            value_start = i
            while i < length and line[i] != '"':
                i += 1
            value = line[value_start:i]
            i += 1
        else:
            # Unquoted value
            value_start = i
            while i < length and not line[i].isspace():
                i += 1
            value = line[value_start:i]
        
        result[key] = value
        
    return result

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    if not intervals:
        return []
    
    sorted_intervals = sorted(intervals)
    
    merged = []
    current_start, current_end = sorted_intervals[0]
    
    for start, end in sorted_intervals[1:]:
        if start <= current_end:
            current_end = max(current_end, end)
        else:
            merged.append((current_start, current_end))
            current_start, current_end = start, end
            
    merged.append((current_start, current_end))
    return merged

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    if not intervals:
        return []

    sorted_intervals = sorted(intervals)
    merged = []

    current_start, current_end = sorted_intervals[0]

    for start, end in sorted_intervals[1:]:
        if start <= current_end:
            current_end = max(current_end, end)
        else:
            merged.append((current_start, current_end))
            current_start, current_end = start, end

    merged.append((current_start, current_end))
    return merged

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    if not intervals:
        return []
    
    # Sort intervals by start time; sorted() returns a new list so input is unchanged
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    
    merged = []
    current_start, current_end = sorted_intervals[0]
    
    for start, end in sorted_intervals[1:]:
        # Merge if intervals overlap or touch
        if start <= current_end:
            current_end = max(current_end, end)
        else:
            merged.append((current_start, current_end))
            current_start, current_end = start, end
    
    merged.append((current_start, current_end))
    return merged

from datetime import date

def add_months(d: date, months: int) -> date:
    year = d.year
    month = d.month + months

    while month <= 0:
        month += 12
        year -= 1
    while month > 12:
        month -= 12
        year += 1

    day = d.day
    try:
        return date(year, month, day)
    except ValueError:
        return date(year, month, 1) - timedelta(days=1)

from datetime import timedelta

import datetime
import calendar

def add_months(d: datetime.date, months: int) -> datetime.date:
    year = d.year
    month = d.month
    day = d.day
    
    # Calculate new month and year
    shifted = month - 1 + months
    new_month = (shifted % 12) + 1
    year += shifted // 12
    
    # Determine valid day in the target month
    days_in_target_month = calendar.monthrange(year, new_month)[1]
    final_day = min(day, days_in_target_month)
    
    return datetime.date(year, new_month, final_day)

import datetime
import calendar

def add_months(d: datetime.date, months: int) -> datetime.date:
    m = d.month
    y = d.year
    total_months = m + months
    new_year = y + (total_months - 1) // 12
    new_month = ((total_months - 1) % 12) + 1
    
    day = d.day
    max_day = calendar.monthrange(new_year, new_month)[1]
    
    if day > max_day:
        day = max_day
        
    return datetime.date(new_year, new_month, day)

import re
from collections import Counter

def top_k_words(text: str, k: int) -> list[tuple[str, int]]:
    words = re.findall(r"[a-z']+", text.lower())
    counts = Counter(words)
    return sorted(counts.items(), key=lambda x: (-x[1], x[0]))[:k]

import re
from collections import Counter

def top_k_words(text: str, k: int) -> list[tuple[str, int]]:
    words = re.findall(r"[A-Za-z']+", text)
    words = [w.lower() for w in words]
    counts = Counter(words)
    return sorted(counts.items(), key=lambda x: (-x[1], x[0]))[:k]

def flatten(obj: dict, sep: str = ".") -> dict:
    result = {}

    def _flatten(prefix: str, value):
        if isinstance(value, dict):
            for key, val in value.items():
                new_prefix = f"{prefix}{sep}{key}" if prefix else key
                _flatten(new_prefix, val)
        elif isinstance(value, list):
            for i, val in enumerate(value):
                new_prefix = f"{prefix}{sep}{i}" if prefix else str(i)
                _flatten(new_prefix, val)
        else:
            result[prefix] = value

    _flatten("", obj)
    return result

def flatten(obj: dict, sep: str = ".") -> dict:
    result = {}
    
    def flatten_helper(current_obj: dict, prefix: str = ""):
        for key, value in current_obj.items():
            new_key = f"{prefix}{key}" if prefix else key
            
            if isinstance(value, dict):
                if value:
                    flatten_helper(value, new_key + sep)
                else:
                    result[new_key] = {}
            elif isinstance(value, list):
                for i, item in enumerate(value):
                    if isinstance(item, dict):
                        if item:
                            flatten_helper(item, new_key + sep + str(i) + sep)
                        else:
                            result[new_key + sep + str(i)] = {}
                    else:
                        result[new_key + sep + str(i)] = item
            else:
                result[new_key] = value
    
    flatten_helper(obj)
    return result

from typing import Any, Dict

def flatten(obj: Dict[str, Any], sep: str = ".") -> Dict[str, Any]:
    result: Dict[str, Any] = {}
    
    def flatten_recursive(current: Any, prefix: str = ""):
        if isinstance(current, dict):
            if not current:
                if prefix:
                    result[prefix] = {}
                return
            for key, value in current.items():
                new_key = f"{prefix}{sep}{key}" if prefix else key
                flatten_recursive(value, new_key)
        elif isinstance(current, list):
            if not current:
                if prefix:
                    result[prefix] = []
                return
            for i, value in enumerate(current):
                new_key = f"{prefix}{sep}{i}" if prefix else str(i)
                flatten_recursive(value, new_key)
        else:
            if prefix:
                result[prefix] = current
    
    flatten_recursive(obj)
    return result

from collections import OrderedDict
from functools import wraps

def lru(maxsize: int):
    def decorator(func):
        cache = OrderedDict()
        
        @wraps(func)
        def wrapper(*args, **kwargs):
            key = args + tuple(sorted(kwargs.items()))
            
            if key in cache:
                cache.move_to_end(key)
                return cache[key]
            
            if len(cache) >= maxsize:
                cache.popitem(last=False)
            
            cache[key] = func(*args, **kwargs)
            return cache[key]
        
        return wrapper
    return decorator

from collections import OrderedDict

def lru(maxsize: int):
    class LRUCache:
        def __init__(self, maxsize: int):
            self._cache = OrderedDict()
            self._maxsize = maxsize

        def get(self, key):
            if key in self._cache:
                self._cache.move_to_end(key)
                return self._cache[key]
            return None

        def set(self, key, value):
            self._cache[key] = value
            if len(self._cache) > self._maxsize:
                self._cache.popitem(last=False)

    def decorator(func):
        cache = LRUCache(maxsize)

        def wrapper(*args, **kwargs):
            key = (args, tuple(sorted(kwargs.items())))
            if cached := cache.get(key):
                return cached
            result = func(*args, **kwargs)
            cache.set(key, result)
            return result

        wrapper.__name__ = func.__name__
        return wrapper

    return decorator

from collections import OrderedDict

def lru(maxsize: int):
    def decorator(func):
        if maxsize <= 0:
            return func
        
        cache = OrderedDict()
        
        def wrapper(*args, **kwargs):
            key = args
            if key in cache:
                cache.move_to_end(key)
                return cache[key]
            
            if len(cache) >= maxsize:
                cache.popitem(last=False)
            
            cache[key] = func(*args, **kwargs)
            return cache[key]
        
        wrapper.__name__ = func.__name__
        return wrapper
    return decorator