Run Detail

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 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 = []
    current_char = s[0]
    count = 1
    
    for i in range(1, len(s)):
        if s[i] == current_char:
            count += 1
        else:
            result.append(current_char + str(count))
            current_char = s[i]
            count = 1
    
    result.append(current_char + str(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)):
        if s[i] == current_char:
            count += 1
        else:
            result.append(f"{current_char}{count}")
            current_char = s[i]
            count = 1
    result.append(f"{current_char}{count}")
    return "".join(result)

def rle(s: str) -> str:
    if not s:
        return ""
    result = []
    current_char = s[0]
    count = 1
    for char in s[1:]:
        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)

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

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 decimal import Decimal, ROUND_HALF_UP

def round_half_up(value: str, digits: int) -> str:
    d = Decimal(value)
    if digits == 0:
        rounded = d.quantize(Decimal('1'), rounding=ROUND_HALF_UP)
        return str(rounded)
    else:
        quantize_str = '0.' + '0' * digits
        rounded = d.quantize(Decimal(quantize_str), rounding=ROUND_HALF_UP)
        return str(rounded)

def round_half_up(value: str, digits: int) -> str:
    negative = value[0] == '-'
    if negative:
        value = value[1:]
    
    if '.' in value:
        integer_part, fractional_part = value.split('.', 1)
    else:
        integer_part, fractional_part = value, ""
    
    if digits == 0:
        # Round to integer, round half up
        fractional = fractional_part.ljust(1, '0') if fractional_part else "0"
        round_up = int(fractional[0]) >= 5
        rounded = int(integer_part) + (1 if negative and round_up else round_up)
        # Handle negative with round up correctly
        if negative and round_up:
            rounded = -(int(integer_part) + 1)
        else:
            rounded = int(integer_part) + round_up
        return str(rounded)
    
    # Pad fractional part to digits + 1 to check rounding digit
    fractional = fractional_part.ljust(digits + 1, '0')
    
    # Check rounding digit and remaining
    round_digit = int(fractional[digits])
    remaining = fractional[digits + 1:]
    
    # Round up if: digit > 5, or digit == 5 with non-zero remaining, or digit == 5 with zero remaining (exact tie)
    round_up = round_digit > 5 or (round_digit == 5 and (remaining != "0" or len(fractional) == digits + 1))
    
    # Determine the number to add to integer part
    if digits == 0:
        rounded_int = int(integer_part) + (1 if round_up else 0)
        if negative:
            rounded_int = -rounded_int
        result = str(rounded_int)
    else:
        # Determine rounded fractional part
        rounded_fractional = fractional[:digits]
        
        # If rounding up, increment the integer part and handle carry
        if round_up:
            rounded_int = int(integer_part) + 1
            if rounded_int == 0:
                rounded_int = 0  # Handle case like "0.999" -> "1.000"
            # Adjust fractional part for carry
            rounded_fractional = str(rounded_int % 10) if rounded_int % 10 != 0 else "0"
        
        result = f"{int(integer_part) if not round_up or not round_up else int(integer_part) + 1}.{rounded_fractional}"
        if negative:
            result = "-" + result.lstrip('-')
    
    # Better approach: build result directly
    if digits == 0:
        # Simple integer rounding
        shifted = float(value) * 10
        rounded = int(shifted + (0.5 if negative else -0.5)) if negative else int(shifted + 0.5)
        return str(rounded)
    
    # Build result with proper rounding
    int_len = len(integer_part)
    frac_start = int_len + 1
    
    # Extract the part that determines rounding
    rounding_value = float(value)
    multiplier = 10 ** digits
    
    # Use string approach for precision
    if fractional_part:
        # Find where the rounding digit is
        round_check = fractional_part[:digits] + fractional_part[digits] + fractional_part[digits+1:] if len(fractional_part) > digits else fractional_part[:digits] + "0"
    else:
        round_check = "0"
    
    # Round based on the digit
    if len(rounding_value) > 0:
        rounded_float = float(value)
        scaled = rounded_float * (10 ** digits)
        # Round half up
        scaled_up = int(scaled + (0.5 if scaled >= 0 else -0.5))
        result = scaled_up / (10 ** digits)
        result_str = f"{result:.{digits}f}"
        if negative and float(value) < 0:
            result_str = result_str.lstrip('-')
            result_str = "-" + result_str
        return result_str
    
    return value

def round_half_up(value: str, digits: int) -> str:
    negative = value.startswith('-')
    if negative:
        value = value[1:]
    
    if '.' not in value:
        int_part = value
        decimal_part = ''
    else:
        int_part, decimal_part = value.split('.', 1)
    
    # Pad decimal part with zeros to the desired length
    decimal_part = decimal_part.ljust(digits, '0')
    
    # Determine rounding position
    round_digit = int(decimal_part[digits]) if len(decimal_part) > digits else 0
    rest = decimal_part[digits+1:] if len(decimal_part) > digits + 1 else ''
    
    # Check if we need to round up
    round_up = False
    if round_digit > 5:
        round_up = True
    elif round_digit == 5:
        # Round up if there are non-zero digits after the 5
        if rest:
            round_up = any(c != '0' for c in rest)
        else:
            # Exact 5 with no following digits: round up for positive, down for negative
            # But we already removed the sign, so round up
            round_up = True
    
    if digits == 0:
        result = int_part + ('1' if round_up else '')
        if round_up and int_part and int_part[-1] == '9':
            parts = result[:-1]
            more = int(parts) + 1
            result = str(more)
    else:
        # Apply rounding to decimal_part
        decimal_part = decimal_part[:digits]
        if round_up:
            val = int(decimal_part) + 1
            decimal_part = str(val)
            while len(decimal_part) > digits:
                decimal_part = decimal_part[:-1] + str(int(decimal_part[-1]) + 1)
                if len(decimal_part) <= digits:
                    break
        
        result = int_part + '.' + decimal_part.ljust(digits, '0')
    
    if negative:
        result = '-' + result
    
    return result

def parse_kv(line: str) -> dict[str, str]:
    result = {}
    if not line or not line.strip():
        return result

    i = 0
    n = len(line)

    while i < n:
        # Skip leading whitespace
        while i < n and line[i] in ' \t':
            i += 1

        if i >= n:
            break

        # Parse key (stops at space, tab, or equals)
        key_start = i
        while i < n and line[i] not in ' \t=:':
            i += 1

        key = line[key_start:i]

        # Skip whitespace before '='
        while i < n and line[i] in ' \t':
            i += 1

        if i >= n or line[i] != '=':
            continue

        i += 1  # Skip '='

        # Skip whitespace after '='
        while i < n and line[i] in ' \t':
            i += 1

        # Parse value
        value_start = i
        if i < n and line[i] == '"':
            # Quoted value
            i += 1  # Skip opening quote
            while i < n and line[i] != '"':
                i += 1
            if i < n:
                i += 1  # Skip closing quote
            value = line[value_start:i]
        else:
            # Unquoted value
            while i < n and line[i] not in ' \t':
                i += 1
            value = line[value_start:i]

        result[key] = value

    return result

def parse_kv(line: str) -> dict[str, str]:
    result = {}
    n = len(line)
    i = 0
    while i < n:
        # Skip whitespace
        while i < n and line[i].isspace():
            i += 1
        if i == n:
            break
        
        # Find '=' for key
        eq_pos = line.find('=', i)
        if eq_pos == -1:
            break
        
        # Extract key
        key = line[i:eq_pos].strip()
        i = eq_pos + 1
        
        # Extract value
        value = ""
        if i < n and line[i] == '"':
            # Quoted value
            i += 1
            end_quote = line.find('"', i)
            if end_quote != -1:
                value = line[i:end_quote]
                i = end_quote + 1
            else:
                # Unclosed quote, treat rest as value
                value = line[i:]
                i = n
        else:
            # Unquoted value
            while i < n and not line[i].isspace():
                i += 1
            value = line[eq_pos + 1 : i]
        
        result[key] = value
    return result

def parse_kv(line: str) -> dict[str, str]:
    if not line:
        return {}
    result = {}
    i = 0
    n = len(line)
    while i < n:
        # Skip leading whitespace
        while i < n and line[i].isspace():
            i += 1
        if i >= n:
            break

        # Find '=' for key
        eq_idx = line.find('=', i)
        if eq_idx == -1:
            break
        
        key = line[i:eq_idx]
        i = eq_idx + 1
        
        # Skip whitespace after '='
        while i < n and line[i].isspace():
            i += 1
        
        val_start = i
        if i >= n:
            val = ""
        elif line[i] == '"':
            # Quoted value
            close_quote = line.find('"', i + 1)
            if close_quote == -1:
                # No closing quote, treat rest as value? 
                # Assuming valid input, but handling gracefully.
                val = line[i+1:]
                i = n
            else:
                val = line[i+1:close_quote]
                i = close_quote + 1
        else:
            # Unquoted value
            while i < n and not line[i].isspace():
                i += 1
            val = line[val_start:i]
        
        result[key] = val

    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, key=lambda x: x[0])
    merged = [sorted_intervals[0]]
    
    for start, end in sorted_intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:
            merged[-1] = (last_start, max(last_end, end))
        else:
            merged.append((start, 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

import datetime

def add_months(d: datetime.date, months: int) -> datetime.date:
    if months == 0:
        return d

    year = d.year
    month = d.month
    day = d.day

    # Calculate year and month offset
    year += months // 12
    month += months % 12

    # Normalize month to 1-12 range using modulo
    month = (month - 1) % 12 + 1

    # Try to create the date with the original day
    try:
        return datetime.date(year, month, day)
    except ValueError:
        # Day doesn't exist in target month, use last day
        return datetime.date(year, month, 1) - datetime.timedelta(days=1)

import datetime

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

    # Adjust month and year
    month += months
    while month <= 0:
        month += 12
        year -= 1
    while month > 12:
        month -= 12
        year += 1

    # Try to create the date
    try:
        return datetime.date(year, month, day)
    except ValueError:
        # If day does not exist in the target month, use the last day
        if month == 12:
            next_year = year + 1
            next_month = 1
        else:
            next_year = year
            next_month = month + 1

        first_day_next = datetime.date(next_year, next_month, 1)
        return first_day_next - datetime.timedelta(days=1)

from datetime import date
import calendar

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

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

    try:
        return date(year, month, d.day)
    except ValueError:
        return date(year, month, calendar.monthrange(year, month)[1])

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)
    counts = Counter(word.lower() for word in words)
    sorted_words = sorted(counts.items(), key=lambda x: (-x[1], x[0]))
    return sorted_words[: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]
    counter = Counter(words)
    return sorted(counter.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)
    counts = Counter(word.lower() for word in words)
    return sorted(counts.items(), key=lambda item: (-item[1], item[0]))[:k]

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

    def flatten_recursive(current_obj, current_path):
        if isinstance(current_obj, dict):
            if not current_obj:
                result[current_path] = current_obj
                return
            for key, value in current_obj.items():
                new_path = f"{current_path}{sep}{key}" if current_path else str(key)
                flatten_recursive(value, new_path)
        elif isinstance(current_obj, list):
            if not current_obj:
                result[current_path] = current_obj
                return
            for i, value in enumerate(current_obj):
                new_path = f"{current_path}{sep}{i}" if current_path else str(i)
                flatten_recursive(value, new_path)
        else:
            result[current_path] = current_obj

    flatten_recursive(obj, "")
    return result

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

    def _flatten(current_prefix: str, value: any) -> None:
        if isinstance(value, dict):
            if not value:
                if current_prefix:
                    result[current_prefix] = {}
            else:
                for k, v in value.items():
                    new_key = f"{current_prefix}{sep}{k}" if current_prefix else k
                    _flatten(new_key, v)
        elif isinstance(value, list):
            for i, v in enumerate(value):
                new_key = f"{current_prefix}{sep}{i}" if current_prefix else str(i)
                _flatten(new_key, v)
        else:
            if current_prefix:
                result[current_prefix] = value

    for k, v in obj.items():
        _flatten(k, v)

    # After processing all keys, add empty dicts that were already handled
    # But we need to check if keys were added correctly
    # Actually the issue is that empty dict with no children won't be added
    # We need to handle empty dicts at any level

    def _ensure_empty_dict(prefix: str, value: any) -> None:
        if isinstance(value, dict):
            if not value:
                if prefix:
                    result[prefix] = {}
            else:
                for k, v in value.items():
                    new_key = f"{prefix}{sep}{k}" if prefix else k
                    _ensure_empty_dict(new_key, v)
        elif isinstance(value, list):
            for i, v in enumerate(value):
                new_key = f"{prefix}{sep}{i}" if prefix else str(i)
                _ensure_empty_dict(new_key, v)
        # Non-dict values are handled in flatten

    return result

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

    def _flatten(current_prefix: str, value: any) -> None:
        if isinstance(value, dict):
            if not value:
                if current_prefix:
                    result[current_prefix] = {}
            else:
                for k, v in value.items():
                    new_key = f"{current_prefix}{sep}{k}" if current_prefix else k
                    _flatten(new_key, v)
        elif isinstance(value, list):
            for i, v in enumerate(value):
                new_key = f"{current_prefix}{sep}{i}" if current_prefix else str(i)
                _flatten(new_key, v)
        else:
            if current_prefix:
                result[current_prefix] = value

    for k, v in obj.items():
        _flatten(k, v)

    return result

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

    def _flatten(current_obj: dict | list, prefix: str = "") -> None:
        if isinstance(current_obj, dict):
            for key, value in current_obj.items():
                new_key = f"{prefix}{key}" if prefix else key
                if isinstance(value, dict) and value:
                    _flatten(value, new_key + sep)
                elif isinstance(value, list) and value:
                    _flatten(value, new_key + sep)
                else:
                    result[new_key] = value
        elif isinstance(current_obj, list):
            for i, value in enumerate(current_obj):
                new_key = f"{prefix}{i}" if prefix else str(i)
                if isinstance(value, dict) and value:
                    _flatten(value, new_key + sep)
                elif isinstance(value, list) and value:
                    _flatten(value, new_key + sep)
                else:
                    result[new_key] = value

    _flatten(obj)
    return result

from collections import OrderedDict

def lru(maxsize: int):
    def decorator(func):
        cache = OrderedDict()

        def wrapper(*args, **kwargs):
            if args in cache:
                cache.move_to_end(args)
                return cache[args]

            result = func(*args, **kwargs)
            cache[args] = result

            while len(cache) > maxsize:
                cache.popitem(last=False)

            return result

        wrapper.__name__ = func.__name__
        return wrapper

    return decorator

from typing import Any, Callable, Dict, List

class LRUCache:
    def __init__(self, maxsize: int):
        self.maxsize = maxsize
        self.cache: Dict[tuple, Any] = {}
        self.keys: List[tuple] = []

    def get(self, key: tuple) -> Any:
        if key in self.cache:
            self.keys.remove(key)
            self.keys.append(key)
            return self.cache[key]
        return None

    def put(self, key: tuple, value: Any) -> None:
        if key in self.cache:
            self.keys.remove(key)
            self.keys.append(key)
            self.cache[key] = value
        else:
            self.cache[key] = value
            self.keys.append(key)
            if len(self.cache) > self.maxsize:
                lru_key = self.keys.pop(0)
                del self.cache[lru_key]

def lru(maxsize: int):
    def decorator(func: Callable) -> Callable:
        cache = LRUCache(maxsize)

        def wrapper(*args, **kwargs):
            key = args
            result = cache.get(key)
            if result is not None:
                return result
            result = func(*args, **kwargs)
            cache.put(key, result)
            return result

        wrapper.__name__ = func.__name__
        return wrapper

    return decorator

class LRUCache:
    def __init__(self, maxsize: int):
        self.maxsize = maxsize
        self.cache = {}
        self.order = []

    def get(self, key):
        if key in self.cache:
            self.order.remove(key)
            self.order.append(key)
            return self.cache[key]
        return None

    def put(self, key, value):
        if key in self.cache:
            self.order.remove(key)
            self.order.append(key)
            self.cache[key] = value
        else:
            if len(self.cache) >= self.maxsize:
                lru_key = self.order.pop(0)
                del self.cache[lru_key]
            self.cache[key] = value
            self.order.append(key)

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

        def wrapper(*args, **kwargs):
            key = (args, tuple(sorted(kwargs.items())))
            result = cache.get(key)
            if result is not None:
                return result
            result = func(*args, **kwargs)
            cache.put(key, result)
            return result

        wrapper.__name__ = func.__name__
        wrapper.__doc__ = func.__doc__
        wrapper.__wrapped__ = func
        return wrapper

    return decorator