Run Detail

def is_leap(year: int) -> bool:
    """Return True if the given Gregorian year is a leap year."""
    return (year % 4 == 0) and ((year % 100 != 0) or (year % 400 == 0))

def is_leap(year: int) -> bool:
    """Return True if year is a leap year in the Gregorian calendar."""
    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 ch in s[1:]:
        if ch == current_char:
            count += 1
        else:
            result.append(current_char + str(count))
            current_char = ch
            count = 1
    result.append(current_char + str(count))
    return ''.join(result)

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

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

def chunks(items, n: int) -> list[list]:
    if n < 1:
        raise ValueError("n must be >= 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 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 = []
        for _ in range(n):
            try:
                chunk.append(next(it))
            except StopIteration:
                break
        if not chunk:
            break
        result.append(chunk)
    return result

def round_half_up(value: str, digits: int) -> str:
    from decimal import Decimal, ROUND_HALF_UP, getcontext
    # Set precision sufficiently large for the operation
    prec = max(len(value.replace('.', '').replace('-', '').replace('+', '')), digits + 10, 28)
    getcontext().prec = prec
    d = Decimal(value)
    exp = Decimal('1e-{}'.format(digits)) if digits else Decimal('1')
    rounded = d.quantize(exp, rounding=ROUND_HALF_UP)
    return format(rounded, 'f')

from decimal import Decimal, ROUND_HALF_UP

def round_half_up(value: str, digits: int) -> str:
    d = Decimal(value)
    if digits == 0:
        quant = Decimal('1')
    else:
        quant = Decimal(f'1e-{digits}')
    rounded = d.quantize(quant, rounding=ROUND_HALF_UP)
    return format(rounded, 'f') if digits > 0 else str(rounded)

from decimal import Decimal, ROUND_HALF_UP

def round_half_up(value: str, digits: int) -> str:
    """Round a decimal number represented as a string to a given number of decimal places,
    rounding half up (away from zero). Returns a string with exactly `digits` decimal
    places, omitting the decimal point when `digits` is 0."""
    d = Decimal(value)
    if digits == 0:
        exp = Decimal('1')
    else:
        exp = Decimal('1.' + '0' * digits)
    rounded = d.quantize(exp, rounding=ROUND_HALF_UP)
    return format(rounded, 'f')

def parse_kv(line: str) -> dict[str, str]:
    i = 0
    n = len(line)
    result: dict[str, str] = {}
    while i < n:
        # skip whitespace
        while i < n and line[i].isspace():
            i += 1
        if i >= n:
            break
        # read key up to '='
        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]:
    result = {}
    i, n = 0, len(line)
    while i < n:
        # Skip whitespace between pairs
        while i < n and line[i].isspace():
            i += 1
        if i >= n:
            break

        # Read key up to '='
        start = i
        while i < n and line[i] != '=':
            i += 1
        if i >= n:
            break  # No '=', ignore rest
        key = line[start:i]
        i += 1  # Skip '='

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

        result[key] = value

    return result

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

        # Parse key up to '='
        key_start = i
        while i < n and line[i] != '=':
            i += 1
        if i >= n:
            break  # no '=' found
        key = line[key_start:i]
        i += 1  # skip '='

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

        result[key] = value
    return result

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Merge overlapping or touching intervals, returning a new sorted list."""
    # Make a sorted copy of the input intervals
    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

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: list[tuple[int, int]] = [sorted_intervals[0]]
    for start, end in sorted_intervals[1:]:
        prev_start, prev_end = merged[-1]
        if start <= prev_end:
            merged[-1] = (prev_start, max(prev_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 []

    # Work on a sorted copy to keep the original list unchanged
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    merged: list[tuple[int, int]] = [sorted_intervals[0]]

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

    return merged

import calendar
from datetime import date

def add_months(d: date, months: int) -> date:
    """Add or subtract calendar months to a date."""
    # Compute the total number of months since year 0
    total_months = d.year * 12 + (d.month - 1) + months
    new_year = total_months // 12
    new_month = total_months % 12 + 1
    # Find the last day of the target month
    last_day = calendar.monthrange(new_year, new_month)[1]
    # Use the smaller of the original day or the last day of the target month
    new_day = min(d.day, last_day)
    return date(new_year, new_month, new_day)

import datetime
import calendar

def add_months(d: datetime.date, months: int) -> datetime.date:
    month_index = d.month - 1 + months
    new_year = d.year + month_index // 12
    new_month = month_index % 12 + 1
    last_day = calendar.monthrange(new_year, new_month)[1]
    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:
    """Add `months` calendar months to `d`, handling month-end overflow."""
    # Convert month to zero-based index and add months
    total_months = d.month - 1 + months
    new_year = d.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)[1]
    new_day = min(d.day, last_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]]:
    if k <= 0:
        return []
    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
import collections
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)
    words_lower = [w.lower() for w in words]
    counter = collections.Counter(words_lower)
    sorted_items = sorted(counter.items(), key=lambda item: (-item[1], item[0]))
    return sorted_items[: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: dict = {}

    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 str(k)
                _flatten(v, new_prefix)
        elif isinstance(current, list):
            if not current:
                result[prefix] = []
                return
            for i, item in enumerate(current):
                new_prefix = f"{prefix}{sep}{i}" if prefix else str(i)
                _flatten(item, new_prefix)
        else:
            result[prefix] = current

    _flatten(obj, "")
    return result

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

    def _process(current, path: str) -> None:
        if isinstance(current, dict):
            if not current:
                result[path] = {}
            else:
                for k, v in current.items():
                    new_path = f"{path}{sep}{k}" if path else k
                    _process(v, new_path)
        elif isinstance(current, list):
            if not current:
                result[path] = []
            else:
                for idx, item in enumerate(current):
                    new_path = f"{path}{sep}{idx}" if path else str(idx)
                    _process(item, new_path)
        else:
            result[path] = current

    _process(obj, "")
    return result

def flatten(obj: dict, sep: str = ".") -> dict:
    """
    Flatten nested dictionaries and lists into a single-level dictionary.

    Parameters
    ----------
    obj : dict
        The dictionary to flatten.
    sep : str, optional
        Separator used to join keys, by default ".".

    Returns
    -------
    dict
        A flattened dictionary.
    """
    result: dict[str, object] = {}

    def _flatten(value: object, path: str) -> None:
        if isinstance(value, dict):
            if not value:  # empty dict
                result[path] = {}
                return
            for k, v in value.items():
                new_path = f"{path}{sep}{k}" if path else str(k)
                _flatten(v, new_path)
        elif isinstance(value, list):
            if not value:  # empty list
                result[path] = []
                return
            for idx, item in enumerate(value):
                new_path = f"{path}{sep}{idx}" if path else str(idx)
                _flatten(item, new_path)
        else:
            result[path] = value

    _flatten(obj, "")
    return result

from typing import Callable, Any

def lru(maxsize: int) -> Callable[[Callable[..., Any]], Callable[..., Any]]:
    def decorator(func: Callable[..., Any]) -> Callable[..., Any]:
        if maxsize <= 0:
            return func
        cache: dict[tuple[Any, ...], Any] = {}

        def wrapper(*args: Any, **kwargs: Any) -> Any:
            key = args
            if key in cache:
                value = cache[key]
                # Move key to the end to mark it as recently used
                del cache[key]
                cache[key] = value
                return value
            result = func(*args, **kwargs)
            cache[key] = result
            if len(cache) > maxsize:
                # Evict the least recently used item (first inserted)
                first_key = next(iter(cache))
                cache.pop(first_key)
            return result

        wrapper.__name__ = func.__name__
        wrapper.__doc__ = func.__doc__
        wrapper.__module__ = func.__module__
        return wrapper

    return decorator

import collections
import functools

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

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

        return wrapper

    return decorator

import collections

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

        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

        wrapper.__name__ = func.__name__
        return wrapper
    return decorator