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 ""
    parts = []
    current = s[0]
    count = 1
    for ch in s[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(current + str(count))
            current = ch
            count = 1
    parts.append(current + str(count))
    return "".join(parts)

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

def rle(s: str) -> str:
    if not s:
        return ""
    result = []
    prev = s[0]
    count = 1
    for ch in s[1:]:
        if ch == prev:
            count += 1
        else:
            result.append(prev + str(count))
            prev = ch
            count = 1
    result.append(prev + str(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

import itertools
from typing import Iterable, List

def chunks(items: Iterable, n: int) -> List[List]:
    if n < 1:
        raise ValueError("n must be at least 1")
    it = iter(items)
    result: List[List] = []
    while True:
        chunk = list(itertools.islice(it, 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 = []
    chunk = []
    for item in items:
        chunk.append(item)
        if len(chunk) == n:
            result.append(chunk)
            chunk = []
    if chunk:
        result.append(chunk)
    return result

from decimal import Decimal, ROUND_HALF_UP

def round_half_up(value: str, digits: int) -> str:
    """
    Round the decimal number represented by `value` to `digits` decimal places,
    using half-up rounding (rounding ties away from zero). Return the result
    as a string with exactly `digits` decimal places; omit the decimal point
    when `digits` is 0.
    """
    d = Decimal(value)
    if digits == 0:
        q = Decimal('1')
    else:
        q = Decimal('1.' + '0' * digits)
    rounded = d.quantize(q, rounding=ROUND_HALF_UP)
    return str(rounded)

def round_half_up(value: str, digits: int) -> str:
    from decimal import Decimal, ROUND_HALF_UP

    d = Decimal(value)
    if digits == 0:
        quant = Decimal("1")
    else:
        quant = Decimal(f"1e-{digits}")
    rounded = d.quantize(quant, rounding=ROUND_HALF_UP)

    # Handle signed zero
    if rounded.is_zero():
        return "0" if digits == 0 else "0." + "0" * digits

    s = format(rounded, "f")
    if digits == 0:
        return s.split(".")[0]
    integer_part, frac_part = s.split(".")
    frac_part = (frac_part + "0" * digits)[:digits]
    return f"{integer_part}.{frac_part}"

import decimal

def round_half_up(value: str, digits: int) -> str:
    d = decimal.Decimal(value)
    if digits == 0:
        q = d.quantize(decimal.Decimal('1'), rounding=decimal.ROUND_HALF_UP)
    else:
        exp = decimal.Decimal(f'1e-{digits}')
        q = d.quantize(exp, rounding=decimal.ROUND_HALF_UP)
    s = format(q, 'f')
    if digits == 0 and '.' in s:
        s = s.split('.')[0]
    return s

import typing

def parse_kv(line: str) -> dict[str, str]:
    result: dict[str, str] = {}
    i, n = 0, len(line)
    while i < n:
        # Skip leading spaces
        while i < n and line[i].isspace():
            i += 1
        if i >= n:
            break
        # Read key
        start_key = i
        while i < n and line[i] != '=':
            i += 1
        if i >= n:
            break  # No '=' found, stop parsing
        key = line[start_key:i]
        i += 1  # skip '='
        # Read value
        if i < n and line[i] == '"':
            i += 1  # skip opening quote
            start_val = i
            while i < n and line[i] != '"':
                i += 1
            value = line[start_val:i]
            if i < n and line[i] == '"':
                i += 1  # skip closing quote
        else:
            start_val = i
            while i < n and not line[i].isspace():
                i += 1
            value = line[start_val:i]
        result[key] = value
    return result

def parse_kv(line: str) -> dict[str, str]:
    """Parse a line of key=value pairs, supporting quoted values."""
    result: dict[str, str] = {}
    s = line
    n = len(s)
    i = 0
    while i < n:
        # Skip leading spaces
        while i < n and s[i].isspace():
            i += 1
        if i >= n:
            break

        # Read key
        key_start = i
        while i < n and s[i] != '=':
            i += 1
        if i >= n:
            break  # No '=' found; ignore rest
        key = s[key_start:i]
        i += 1  # Skip '='

        # Read value
        if i < n and s[i] == '"':
            i += 1  # Skip opening quote
            val_start = i
            while i < n and s[i] != '"':
                i += 1
            value = s[val_start:i]
            if i < n:
                i += 1  # Skip closing quote
        else:
            val_start = i
            while i < n and not s[i].isspace():
                i += 1
            value = s[val_start:i]

        result[key] = value

    return result

import shlex
from typing import Dict

def parse_kv(line: str) -> Dict[str, str]:
    if not line.strip():
        return {}
    result: Dict[str, str] = {}
    for token in shlex.split(line):
        if '=' not in token:
            continue
        key, value = token.split('=', 1)
        result[key] = value
    return result

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Merge overlapping or touching intervals.

    The input list is not modified.
    """
    # Make a shallow copy and sort by start time
    sorted_intervals = sorted(intervals, key=lambda x: x[0])

    merged: list[tuple[int, int]] = []

    for start, end in sorted_intervals:
        if not merged or start > merged[-1][1]:
            # No overlap or touch; add new interval
            merged.append((start, end))
        else:
            # Overlap or touch; merge with last interval
            last_start, last_end = merged[-1]
            merged[-1] = (last_start, max(last_end, end))

    return merged

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Return a list of merged intervals sorted by start."""
    # Sort a copy of the intervals by start, then by end
    sorted_intervals = sorted(intervals, key=lambda x: (x[0], x[1]))
    merged: list[tuple[int, int]] = []

    for start, end in sorted_intervals:
        if not merged:
            merged.append((start, end))
        else:
            last_start, last_end = merged[-1]
            if start <= last_end:  # Overlap or touch
                merged[-1] = (last_start, max(last_end, end))
            else:
                merged.append((start, end))

    return merged

from __future__ import annotations
from typing import List, Tuple

def merge_intervals(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    """Merge overlapping or touching intervals."""
    if not intervals:
        return []

    # Work on a sorted copy to avoid modifying the input list.
    sorted_intervals = sorted(intervals, key=lambda x: x[0])

    merged: List[Tuple[int, int]] = []
    cur_start, cur_end = sorted_intervals[0]

    for start, end in sorted_intervals[1:]:
        if start <= cur_end:  # Overlap or touch
            cur_end = max(cur_end, end)
        else:
            merged.append((cur_start, cur_end))
            cur_start, cur_end = start, end

    merged.append((cur_start, cur_end))
    return merged

import datetime
import calendar

def add_months(d: datetime.date, months: int) -> datetime.date:
    """Add `months` calendar months to date `d`, using the last day of month if needed."""
    # Compute target year and month
    total_month = d.month - 1 + months
    new_year = d.year + total_month // 12
    new_month = total_month % 12 + 1
    # Determine maximum day in the target month
    _, max_day = calendar.monthrange(new_year, new_month)
    # Use the smaller of original day and max_day
    new_day = min(d.day, max_day)
    return datetime.date(new_year, new_month, new_day)

import datetime
import calendar

def add_months(d: datetime.date, months: int) -> datetime.date:
    """
    Add `months` calendar months to `d`. If the resulting month has fewer days than `d.day`,
    the day is set to the last day of that month.
    """
    # Compute the target year and month
    total_months = d.year * 12 + (d.month - 1) + months
    new_year = total_months // 12
    new_month = total_months % 12 + 1

    # Determine the last day of the target month
    _, last_day = calendar.monthrange(new_year, new_month)

    # Use the smaller of the original day and the last day of the target month
    new_day = min(d.day, last_day)

    return datetime.date(new_year, new_month, new_day)

import datetime
import calendar

def add_months(d: datetime.date, months: int) -> datetime.date:
    total_months = d.year * 12 + (d.month - 1) + months
    new_year, new_month = divmod(total_months, 12)
    new_month += 1
    max_day = calendar.monthrange(new_year, new_month)[1]
    new_day = min(d.day, max_day)
    return datetime.date(new_year, new_month, new_day)

import re
from collections import Counter
from typing import List, Tuple

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 item: (-item[1], item[0]))
    return sorted_words[:k]

import re
from collections import Counter
from typing import List, Tuple

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
from typing import List, Tuple

def top_k_words(text: str, k: int) -> List[Tuple[str, int]]:
    if k <= 0:
        return []
    words = re.findall(r"[A-Za-z']+", text)
    counts = Counter(word.lower() for word in words)
    sorted_items = sorted(counts.items(), key=lambda item: (-item[1], item[0]))
    return sorted_items[:k]

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

    def _flatten(current, prefix):
        if isinstance(current, dict):
            if not current:
                result[prefix] = {}
                return
            for k, v in current.items():
                new_prefix = f"{prefix}{sep}{k}" if prefix else k
                _flatten(v, new_prefix)
        elif isinstance(current, list):
            if not current:
                result[prefix] = []
                return
            for idx, item in enumerate(current):
                new_prefix = f"{prefix}{sep}{idx}" if prefix else str(idx)
                _flatten(item, new_prefix)
        else:
            result[prefix] = current

    _flatten(obj, "")
    return result

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

    def _flatten(current, path: list[str]) -> None:
        if isinstance(current, dict):
            if not current:
                if path:
                    result[sep.join(path)] = {}
                return
            for key, value in current.items():
                _flatten(value, path + [key])
        elif isinstance(current, list):
            if not current:
                if path:
                    result[sep.join(path)] = []
                return
            for idx, item in enumerate(current):
                _flatten(item, path + [str(idx)])
        else:
            result[sep.join(path)] = current

    _flatten(obj, [])
    return result

from typing import Any, Dict

def flatten(obj: dict, sep: str = ".") -> dict:
    """
    Flatten nested dicts and lists into a single-level dictionary,
    joining keys with `sep` and using list indices as keys.
    Empty dicts or lists are preserved as values.
    """
    if not isinstance(obj, dict):
        raise TypeError("flatten expects a dict as the first argument")

    result: Dict[str, Any] = {}

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

    # Handle the top-level dict
    for top_key, top_val in obj.items():
        _flatten(top_val, str(top_key))

    return result

import functools
from collections import OrderedDict

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

from collections import OrderedDict
from typing import Callable, Any

def lru(maxsize: int) -> Callable[[Callable[..., Any]], Callable[..., Any]]:
    """
    Decorator factory that caches a function's results by its positional arguments.
    The cache holds at most `maxsize` entries, evicting the least recently used one
    when it becomes full. A cache hit counts as a use. The decorated function
    preserves its original __name__.
    """
    def decorator(func: Callable[..., Any]) -> Callable[..., Any]:
        cache: OrderedDict[tuple[Any, ...], Any] = OrderedDict()

        def wrapper(*args: Any, **kwargs: Any) -> Any:
            key = args
            if key in cache:
                # Move the key to the end to mark it as recently used
                value = cache.pop(key)
                cache[key] = value
                return value
            value = func(*args, **kwargs)
            if maxsize > 0:
                if len(cache) >= maxsize:
                    cache.popitem(last=False)  # evict LRU
                cache[key] = value
            return value

        wrapper.__name__ = func.__name__
        return wrapper

    return decorator

import functools
from collections import OrderedDict

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

        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            key = args
            if key in cache:
                cache.move_to_end(key)
                return cache[key]
            result = func(*args, **kwargs)
            cache[key] = result
            cache.move_to_end(key)
            if len(cache) > maxsize:
                cache.popitem(last=False)
            return result

        return wrapper

    return decorator