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 % 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 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)

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(current_char + str(count))
            current_char = char
            count = 1
    
    result.append(current_char + str(count))
    
    return "".join(result)

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

from typing import Iterable, List, TypeVar

T = TypeVar("T")

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

def chunks(items, n: int) -> list[list]:
    if n < 1:
        raise ValueError("n must be greater than or equal to 1")
    result = []
    iterator = iter(items)
    current_chunk = []
    for item in iterator:
        current_chunk.append(item)
        if len(current_chunk) == n:
            result.append(current_chunk)
            current_chunk = []
    if current_chunk:
        result.append(current_chunk)
    return result

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

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

    # Increase precision to handle long decimals without loss before rounding
    getcontext().prec = 50

    # Create Decimal from string to preserve exact value
    d = Decimal(value)

    # Create quantize exponent for target digits
    if digits == 0:
        quantize_exp = Decimal('1')
    else:
        quantize_exp = Decimal(10) ** -digits

    # Round using ROUND_HALF_UP
    rounded = d.quantize(quantize_exp, rounding=ROUND_HALF_UP)

    # Format output: if digits == 0, return integer part as int (no decimal point)
    if digits == 0:
        return str(rounded.to_integral_value())
    else:
        # Ensure exactly 'digits' decimal places are present
        return format(rounded, f'.{digits}f')

import math

def round_half_up(value: str, digits: int) -> str:
    if '.' not in value:
        integer_part = value
        fractional_part = ""
    else:
        integer_part, fractional_part = value.split('.')
    
    if digits < 0:
        raise ValueError("digits must be non-negative")
    
    # Pad or truncate fractional part to match expected length for analysis
    if len(fractional_part) < digits:
        fractional_part = fractional_part.ljust(digits, '0')
    elif len(fractional_part) > digits:
        fractional_part = fractional_part[:digits]
    
    # Get the last digit to round
    last_digit = int(fractional_part[-1]) if fractional_part else 0
    remaining = fractional_part[:-1] if fractional_part else ""
    
    # Determine if rounding up is needed: >= 5 for ties away from zero
    # Since we need to round exact ties away from zero, any digit >= 5 rounds up.
    should_round_up = last_digit >= 5
    
    # Construct the new fractional part
    if should_round_up:
        # Add 1 to the truncated part, handling carries
        # Convert remaining to list of digits for easy manipulation
        digits_list = [int(d) for d in remaining] + [last_digit]
        
        # Actually, simpler: take the first 'digits' digits, then add 1 to the last one if needed
        # But we already sliced. Let's reconstruct properly.
        # We have `remaining` (first `digits` chars) and `last_digit`.
        # We want to increment the number formed by `remaining + last_digit` by 1 if last_digit >= 5?
        # No, standard rounding: look at digit at `digits` position (index `digits` in original fractional).
        # If that digit >= 5, add 1 to the part before it.
        
        # Let's restart the logic cleanly.
        # We have `value`. We want to round to `digits` places.
        # The digit determining round is at index `digits` of the fractional part (0-indexed).
        
        pass
    
    # Re-implementing cleanly:
    # 1. Parse integer and fractional parts.
    # 2. Pad fractional part with zeros to at least `digits` length.
    # 3. Identify the rounding digit (at index `digits`).
    # 4. If rounding digit >= 5, increment the number formed by the first `digits` fractional digits by 1.
    # 5. Handle carry propagation.
    
    if len(fractional_part) < digits:
        fractional_part = fractional_part.ljust(digits + 1, '0') # Need one extra for rounding digit
    else:
        fractional_part = fractional_part[:digits + 1]
    
    # Now fractional_part has exactly digits+1 characters (or more if we padded too much, but we sliced)
    # Actually if original was longer, we sliced to digits+1. If shorter, we padded to digits+1.
    
    first_part = fractional_part[:digits]
    rounding_digit = int(fractional_part[digits])
    
    if rounding_digit >= 5:
        # Add 1 to first_part
        # Convert to list of integers
        parts = [int(c) for c in first_part]
        carry = 1
        for i in range(len(parts) - 1, -1, -1):
            parts[i] += carry
            if parts[i] >= 10:
                parts[i] -= 10
                carry = 1
            else:
                carry = 0
                break
        if carry:
            # Overflow into integer part
            integer_part = str(int(integer_part) + 1)
            parts = [0] + parts
        
        first_part = "".join(str(p) for p in parts)
    
    # Check if digits is 0
    if digits == 0:
        return integer_part
    else:
        return f"{integer_part}.{first_part}"

import math
from decimal import Decimal, ROUND_HALF_UP, getcontext

def round_half_up(value: str, digits: int) -> str:
    if '.' not in value:
        integer_part = value
        fractional_part = ""
    else:
        integer_part, fractional_part = value.split('.')
    
    # Ensure we have enough precision by parsing as Decimal directly
    # This avoids floating-point inaccuracies
    d = Decimal(f"{integer_part}.{fractional_part}")
    
    # Create quantize string for the desired number of decimal places
    if digits == 0:
        quantize_str = "1"
    else:
        quantize_str = "0." + "0" * digits
    
    # Quantize the Decimal
    rounded = d.quantize(Decimal(quantize_str), rounding=ROUND_HALF_UP)
    
    # Convert to string
    result = str(rounded)
    
    # Handle the case where digits is 0: omit decimal point
    if digits == 0:
        return result.split('.')[0]
    
    # Ensure exactly 'digits' decimal places (Decimal might strip trailing zeros)
    parts = result.split('.')
    if len(parts) == 1:
        integer_str = parts[0]
        fractional_str = "0" * digits
    else:
        integer_str = parts[0]
        fractional_str = parts[1]
    
    # Pad or truncate fractional part to exactly 'digits' length
    if len(fractional_str) < digits:
        fractional_str = fractional_str + "0" * (digits - len(fractional_str))
    elif len(fractional_str) > digits:
        fractional_str = fractional_str[:digits]
    
    return f"{integer_str}.{fractional_str}"

def parse_kv(line: str) -> dict[str, str]:
    """
    Parse a string containing key=value pairs separated by one or more spaces.
    Values may be enclosed in double quotes (allowing spaces and '=' inside).
    Repeated keys overwrite previous values. Empty lines return an empty dict.
    """
    result: dict[str, str] = {}
    if not line.strip():
        return result

    tokens = line.split()
    i = 0
    while i < len(tokens):
        key = tokens[i]
        i += 1
        if i >= len(tokens):
            result[key] = ""
            break

        value_token = tokens[i]
        i += 1

        if value_token.startswith('"') and value_token.endswith('"') and len(value_token) >= 2:
            result[key] = value_token[1:-1]
        else:
            result[key] = value_token

    return result

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

    current_key: str | None = None
    current_value_chars: list[str] = []
    in_quotes: bool = False
    i = 0
    n = len(line)

    while i < n:
        char = line[i]

        if in_quotes:
            if char == '"':
                in_quotes = False
            else:
                current_value_chars.append(char)
            i += 1
            continue

        if char == '"':
            in_quotes = True
            i += 1
            continue

        if current_key is None:
            # Collecting key
            if char == ' ' or char == '\t':
                if current_key:
                    current_key = ''.join(current_value_chars)
                    current_value_chars = []
                else:
                    # Skip leading spaces
                    pass
            elif char == '=':
                # Key found, pending value
                current_key = ''.join(current_value_chars)
                current_value_chars = []
                # Mark that we have a key and are expecting value
                # We will assign once we hit space or end or quote
                # Actually, we need to handle the value collection phase
                # Let's restructure logic slightly for clarity in loop
                # If we hit '=', key is set, now we expect value
                pass
            else:
                # Invalid char before '='? Treat as key continuation or error?
                # Problem says key=value, so key comes first.
                # If we see char other than space, =, or " before any key, it starts key.
                # But we already handled space above.
                # So if we are here and current_key is None and char is not space and not ", it must start key.
                # Wait, my logic above: if char is space, I check if key exists.
                # If char is not space and not ", and not =, then it starts key.
                current_key = ''.join(current_value_chars) + char
                current_value_chars = []

        else:
            # We have a current_key being built
            if char == '=':
                # End of key
                current_key = ''.join(current_value_chars)
                current_value_chars = []
            else:
                current_value_chars.append(char)

        i += 1

    # Process the last key-value pair
    if current_key is not None:
        final_key = current_key
        final_value = ''.join(current_value_chars)
        # If we ended with a key but no value (e.g., "c="), value is empty string.
        # If we ended with key and characters, value is those chars.
        # What if line ends with key but no '='? e.g. "abc" -> key="abc", value=""?
        # Or "abc=" -> key="abc", value=""?
        # The logic above: if we see '=', we set key and clear value_chars.
        # If line ends after '=', value_chars is empty, value is "".
        # If line ends after key (no '='), then current_key includes the chars, and value_chars is empty.
        # But wait, my loop logic for "abc" (no =):
        # i=0, char='a': current_key is None, char not space, so current_key='a', value_chars=[]
        # i=1, char='b': current_key is not None, char not '=', so append to value_chars?
        # Ah, error in logic. Once key is set (by seeing '=' or by seeing non-space non-=" at start?), 
        # subsequent chars should go to value? No.
        # Standard parsing: Key is until '='. Value is after '='.
        # My previous state machine was flawed.

    # Let's rewrite cleanly.
    result = {}
    if not line.strip():
        return result

    parts = []
    current_part = []
    in_quotes = False

    for char in line:
        if in_quotes:
            current_part.append(char)
            if char == '"':
                in_quotes = False
        elif char == '"':
            in_quotes = True
        elif char == ' ' or char == '\t':
            if current_part:
                parts.append(''.join(current_part))
                current_part = []
        else:
            current_part.append(char)

    if current_part:
        parts.append(''.join(current_part))

    # Now split by '='
    i = 0
    while i < len(parts):
        if i == len(parts) - 1:
            # Last part has no '=' following it in the split logic above?
            # No, the split logic above just tokenized by space.
            # We need to find '=' within each token? 
            # No, the spec says "key=value pairs separated by one or more spaces".
            # So the tokens are "k=v", "k2=v2".
            # But wait, "A value may be enclosed in double quotes...".
            # So "k = v" -> tokens: "k", "=", "v"? No, separated by spaces.
            # "k=v" is one token. "k = v" -> "k", "=", "v"? 
            # "separated by one or more spaces".
            # Example: "a=1 b=2" -> tokens ["a=1", "b=2"].
            # Example: "a = 1" -> tokens ["a", "=", "1"]? 
            # If there are spaces around =, then = is a separate token.
            # How to distinguish?
            # "key=value pairs separated by one or more spaces".
            # Usually implies the unit is key=value. But if spaces exist around =, 
            # then = becomes a delimiter token.
            # Let's assume the input is a sequence of tokens.
            # We need to reconstruct key=value.
            # Strategy: Iterate tokens. If token has '=', split. 
            # If token is just 'key', then next token must be '=' then next is value?
            # Or maybe the format is strictly "key=value" with optional spaces around the whole pair?
            # "separated by one or more spaces" refers to the pairs.
            # So "a=b c=d" -> 2 pairs.
            # "a = b" -> is this one pair? Or 3 tokens?
            # If "a = b" is one pair, then spaces are ignored inside the pair.
            # But the spec says "separated by... spaces". It doesn't say spaces are ignored inside.
            # However, "A value may be enclosed in double quotes...".
            # Let's assume standard CSV-like or config-like parsing where spaces separate fields.
            # If "a = b" is given, and we split by space, we get ["a", "=", "b"].
            # How to parse?
            # Likely: Find all "key=value" patterns.
            # But spaces can be anywhere?
            # Re-reading: "key=value pairs separated by one or more spaces".
            # This implies the structure is: [space] (key=value) [space] (key=value) ...
            # Inside a pair, there might be spaces? 
            # "A value may be enclosed in double quotes; if so, it may contain spaces".
            # This implies if NOT enclosed, spaces might terminate the value?
            # If value is not quoted, spaces end the value.
            # So "a=b c" -> key=a, val=b; key=c, val=? (empty?) or error?
            # Given "separated by", it implies the pairs are the units.
            # If I have "a= b", is key=a, val= ? Or key=a, val=b?
            # If spaces separate pairs, then "a= b" might be key=a, val= (empty), next pair key=b?
            # But "b" has no value.
            # Let's assume the simplest interpretation: 
            # The line is a sequence of tokens separated by whitespace.
            # Each token is either a key, a value, or a key=value.
            # But how to know?
            # If a token contains '=', it's key=value.
            # If a token is 'key', then the next token MUST be '='? No, that's unlikely.
            # Most likely: The tokens are exactly the keys and values, and '=' is implicit between them?
            # No, "key=value pairs". The '=' is explicit in the string.
            # So we look for '=' in the tokens.
            # If a token has '=', split into key and value.
            # If a token does not have '=', it's a key (and next is value?) or an error?
            # Or maybe the tokens are just the raw characters, and we should not split by space at all?
            # "separated by one or more spaces".
            # This means the parser should split the line by whitespace to get the pairs.
            # So "a=b c=d" -> ["a=b", "c=d"].
            # "a = b" -> ["a", "=", "b"]? That doesn't look like pairs.
            # Unless the spec implies that the '=' is part of the pair and spaces around it are allowed?
            # But if spaces separate pairs, then "a = b" is 3 items.
            # Let's assume the input is well-formed such that splitting by whitespace gives valid "key=value" strings.
            # Except for the case where value is quoted and contains spaces.
            # Example: "a=" b=1" -> ["a=", "b=1"].
            # Example: "a=hello world" -> if not quoted, is it "a=hello" and "world"?
            # Spec: "A value may be enclosed in double quotes; if so, it may contain spaces".
            # Implies if NOT enclosed, it CANNOT contain spaces? Or spaces act as separators?
            # If spaces act as separators for pairs, then "a=hello world" -> pair1="a=hello", pair2="world" (which is invalid).
            # So likely, unquoted values cannot have spaces.
            # Therefore, splitting by whitespace is safe for unquoted values.
            # But what about "a = b"? If spaces separate pairs, then "a", "=", "b" are tokens.
            # This seems broken.
            # Alternative interpretation: The '=' is a literal character, and spaces are delimiters.
            # We should NOT split by space if it's inside a quoted string.
            # So we need a tokenizer that respects quotes.
            # Then we get tokens.
            # Then we look for '=' in each token.
            # If token has '=', split.
            # If token doesn't have '=', it's a key? And we need a value?
            # Maybe the format is: key [space] = [space] value?
            # If so, splitting by space gives [key, =, value].
            # Then we combine key + '=' + value?
            # But then "a=b" (no spaces) -> ["a=b"].
            # So we have two formats mixed?
            # Let's assume the most robust approach:
            # 1. Tokenize respecting quotes.
            # 2. For each token, if it contains '=', split by first '='.
            # 3. If it doesn't contain '=', it's a key. The next token must be '='? No, that's guessing.
            # Let's reconsider the "separated by spaces" part.
            # It probably means the pairs are delimited by spaces.
            # And a pair is defined as key followed by = followed by value.
            # Spaces can appear around =?
            # If "a = b" is valid, then the tokenizer should see "a", "=", "b".
            # How to parse?
            # Maybe we should not split by space at all, but parse character by character, 
            # building key until '=', then building value until space or end or quote?
            # But value might have spaces if quoted.
            # Algorithm:
            # - Start reading key. Stop at '='.
            # - Start reading value. Stop at space (if not quoted).
            # - If space encountered and not quoted, end of value, start next pair.
            # - If quote encountered, toggle quote state.
            # This handles everything.

    result = {}
    if not line.strip():
        return result

    i = 0
    n = len(line)
    current_key_chars = []
    current_value_chars = []
    in_quotes = False
    state = 'KEY'  # 'KEY' or 'VALUE'
    key_found = False

    while i < n:
        char = line[i]

        if state == 'KEY' and not key_found:
            if char == '=':
                key_found = True
                state = 'VALUE'
                current_value_chars = []
                # Save key
                result[''.join(current_key_chars)] = ''.join(current_value_chars)
                # Wait, if key repeats, use last value. So we should assign immediately?
                # Yes, but we haven't finished the key yet?
                # No, key ends at '='. So we have the full key.
                # But we haven't started the value.
                # So we save the key? No, we need to wait for value to set the final value?
                # "If a key repeats, use the last value."
                # So we store (key, value) pairs.
                # Key is complete. Value is pending.
                # We can't assign to result yet because value might be empty or have chars.
                # But we can store the key and wait.
                # Actually, we can just collect the key, then when we hit '=', we finalize key.
                # Then collect value chars. When value ends, we update result[key] = value.
                pass
            elif char.isspace():
                # Space in key? Invalid? Or end of key?
                # If space before '=', invalid? 
                # Assuming well-formed or key ends at space.
                # But key should not have spaces unless quoted? 
                # Keys are usually not quoted in this format.
                # Let's assume key cannot have spaces.
                # So space ends key.
                # But we haven't seen '='.
                # So this is malformed. But let's assume input is valid key=value.
                # So space must be after '=' or between pairs.
                # So if we are in KEY and see space, it's an error or end of key before '='.
                # Given the problem, likely keys don't have spaces.
                # So we just skip? Or break?
                # Let's assume valid input: key starts, then '='. No spaces in key.
                # So space means end of pair or start of next.
                # If we are in KEY and see space, it's unexpected unless key is empty?
                # Let's assume space only appears after '=' or between pairs.
                # So if we see space in KEY state, it's a pair separator?
                # But we haven't seen '='.
                # Maybe the format allows key [space] =?
                # If so, space ends key.
                # Then we need to see '='.
                # Let's assume space terminates the current logical unit.
                # But we need '=' to define the pair.
                # Okay, let's assume the standard: key is until '='. Spaces only around pairs.
                # So if space in KEY, it's an error or we break.
                # But to be safe, let's assume space ends the pair if we see it before '='?
                # No, let's stick to: Key is contiguous non-space non-=" chars?
                # No, if "a = b", key='a', then space, then '=', then space, then 'b'.
                # So space can appear in KEY state if it's before '='.
                # So:
                # State KEY:
                #   char == '=': move to VALUE, save key.
                #   char == ' ': if we are in KEY, it might be a separator before '='.
                #     But we need to collect key. If space, ignore? Or end key?
                #     If "a = b", key='a'. Space is ignored? Or part of delimiter?
                #     Let's assume keys cannot have spaces. So space ends key collection.
                #     But we need '=' to trigger the pair.
                #     So if space, we pause key collection?
                #     Better: Just collect non-space, non-=" chars for key?
                #     No, what if key is "a-b"? '-' is ok.
                #     What if key is "a b"? Space inside key? Unlikely.
                #     Let's assume keys are contiguous non-space.
                #     So space ends key.
                #     Then we need '='.
                #     If we see space, we end key. Then we need to see '='.
                #     But how to track if we ended key?
                #     Let's use a simpler state machine:
                #     State 0: Collecting key. Ignore spaces? No, space might be delimiter.
                #     Let's assume the input is a stream of tokens where tokens are separated by spaces.
                #     And tokens are parsed as key=value if they contain '='.
                #     If token is just key, then next token is '='? No.
                #     Let's go back to the most common interpretation:
                #     Split by whitespace -> list of strings.
                #     Each string is either "key=value" or just "key" (if followed by "=value" in next tokens)?
                #     No, that's too complex.
                #     Let's assume the string contains "key=value" units separated by spaces.
                #     And spaces are not inside values unless quoted.
                #     So we can split by space, but handle quotes.
                #     Algorithm:
                #     1. Split line into tokens, respecting quotes.
                #     2. For each token:
                #        If '=' in token:
                #           split by first '=' -> key, value.
                #           update result[key] = value.
                #        Else:
                #           It's a key. The next token MUST be '='? No.
                #           Maybe the token is the whole pair?
                #           What if "a=" is a token? Then key='a', value=''.
                #           What if "a" is a token? Then key='a', value=? 
                #           Maybe the value is the next token?
                #           But then "a b" -> key='a', val='b'? But no '='.
                #           The spec says "key=value pairs". So '=' is mandatory.
                #           So if a token doesn't have '=', it's an error or incomplete.
                #           Unless the '=' is in the next token? e.g. "a = b".
                #           Tokens: ["a", "=", "b"].
                #           Then we combine?
                #           This is getting complicated.
                #           Let's assume the input is always "key=value" per token, possibly with spaces around '=' inside the token?
                #           No, split by space would break "a = b" into 3 tokens.
                #           So we cannot split by space blindly.
                #           We must parse character by character.

    # Final Plan:
    # Iterate char by char.
    # States:
    #   - collecting_key: accumulate chars. If '=' seen, switch to collecting_value.
    #   - collecting_value: accumulate chars. If space seen (and not in quotes), switch to collecting_next_key.
    #   - collecting_next_key: current pair done. Reset to collecting_key.
    # But value can contain spaces if quoted.
    # So:
    #   - In collecting_key: accumulate until '='.
    #   - In collecting_value: 
    #       If quote: toggle quote, accumulate char.
    #       If not quote and char == space: end of value. Switch to collecting_next_key.
    #       If not quote and char != space: accumulate.
    #   - In collecting_next_key: just skip until next '=' or space?
    #     Actually, after value ends (space), we are ready for next key.
    #     So we go to collecting_key.
    #     But we need to handle the '=' transition.
    #     Revised States:
    #       1. KEY: building key. Ignore spaces? No, spaces separate pairs.
    #          But key itself shouldn't have spaces.
    #          So if space in KEY, ignore? Or end?
    #          Let's assume key is contiguous non-space.
    #          If space, we are done with key? But we haven't seen '='.
    #          This implies "a b" is invalid or "a" is key, "b" is next key?
    #          Let's assume the input is well-formed: "key=value".
    #          So KEY state sees chars until '='.
    #          If space encountered in KEY, it's an error or ignored.
    #          Let's assume spaces are only delimiters between pairs.
    #          So we can skip spaces before '='?
    #          Yes, "a = b" -> "a", "=", "b".
    #          So in KEY state, if char is space, skip.
    #          If char is '=', switch to VALUE.
    #          If char is quote? Start value with quote.
    #       
    #       2. VALUE: building value.
    #          If quote: toggle. Accumulate.
    #          If space and not quote: end of value. Save pair. Switch to KEY.
    #          If not quote and not space: accumulate.
    #          If '=' in value? "value may contain =". So accumulate.
    #       
    #       3. After saving pair, we are in KEY state again.
    #          Skip spaces until next non-space char (which starts key).
    
    result = {}
    if not line.strip():
        return result

    i = 0
    n = len(line)
    current_key_chars = []
    current_value_chars = []
    in_quotes = False
    state = 'KEY'
    key_set = False

    while i < n:
        char = line[i]

        if state == 'KEY':
            if char.isspace():
                # Skip spaces before key or between pairs
                # If we are at start of key, spaces are ignored.
                pass
            elif char == '=':
                # End of key
                key_set = True
                state = 'VALUE'
                current_value_chars = []
                # We have key, waiting for value.
                # Don't save yet.
            elif char == '"':
                # Start of quoted value immediately after key?
                # e.g. "a="b" -> key=a, value="b"? No, value starts with ".
                # So value starts with ".
                # So we transition to VALUE, and in_quotes=True.
                state = 'VALUE'
                in_quotes = True
                current_value_chars = [char]
            else:
                # Invalid char in KEY? Or part of key?
                # Assume part of key.
                current_key_chars.append(char)

        elif state == 'VALUE':
            if in_quotes:
                current_value_chars.append(char)
                if char == '"':
                    in_quotes = False
            else:
                if char.isspace():
                    # End of value
                    # Save the pair
                    result[''.join(current_key_chars)] = ''.join(current_value_chars)
                    # Reset for next pair
                    current_key_chars = []
                    current_value_chars = []
                    key_set = False
                    state = 'KEY'
                    # Skip this space in next iteration? No, loop continues.
                    # But we need to ensure we don't add space to next key.
                    # In KEY state, we skip spaces.
                elif char == '=':
                    # Should not happen in VALUE? 
                    # "value may contain ="
                    # So we append.
                    current_value_chars.append(char)
                else:
                    current_value_chars.append(char)

        elif state == 'KEY' and key_set:
            # This state is redundant. If key_set, we are effectively in VALUE.
            # But we moved to VALUE when we saw '='.
            # So we don't need this state.
            pass

        i += 1

    # Handle last pair if line doesn't end with space
    if current_key_chars or (key_set and current_value_chars):
        # If we ended in VALUE, we have key and value.
        # If we ended in KEY, we have key but no value? 
        # e.g. "a=" -> key='a', value_chars empty. Saved when space or end?
        # My logic above: if space, save. If end of line, not saved.
        # So check if we have a pending pair.
        if key_set:
            # We have key in current_key_chars, and value in current_value_chars.
            # But wait, if we ended in VALUE, current_key_chars is the key.
            # current_value_chars is the value.
            # But if we ended in KEY (e.g. "a"), then key_set is False?
            # No, if we saw '=', key_set becomes True.
            # If line ends with "a=", we saw '=', key_set=True, state=VALUE, value_chars=[].
            # So we need to save if key_set and we are in VALUE state?
            # Or if we are in KEY state but key_set is True?
            # My state machine: if '=' seen, state becomes VALUE.
            # So if we end loop, state is either KEY or VALUE.
            # If state is VALUE, we have pending pair.
            # If state is KEY, we have pending key but no '='? 
            # e.g. "abc". key='abc', key_set=False. No pair.
            # e.g. "a=" -> state=VALUE, value_chars=[]. key_set=True.
            # So if state == 'VALUE' and key_set:
            if state == 'VALUE' and key_set:
                result[''.join(current_key_chars)] = ''.join(current_value_chars)

    return result

def parse_kv(line: str) -> dict[str, str]:
    if not line.strip():
        return {}
    
    result: dict[str, str] = {}
    i = 0
    n = len(line)
    
    while i < n:
        # Skip leading spaces
        while i < n and line[i] == ' ':
            i += 1
        if i >= n:
            break
        
        # Parse key
        key_start = i
        while i < n and line[i] not in ' =':
            i += 1
        key = line[key_start:i]
        
        if not key:
            break
            
        # Skip spaces before '='
        while i < n and line[i] == ' ':
            i += 1
        
        if i >= n or line[i] != '=':
            # If there's no '=' after the key, stop parsing
            break
            
        i += 1 # Skip '='
        
        # Skip spaces after '='
        while i < n and line[i] == ' ':
            i += 1
        
        if i >= n:
            value = ""
        else:
            # Check for quoted value
            if line[i] == '"':
                i += 1 # Skip opening quote
                value_start = i
                value_chars = []
                while i < n and line[i] != '"':
                    value_chars.append(line[i])
                    i += 1
                if i < n:
                    i += 1 # Skip closing quote
                value = "".join(value_chars)
            else:
                # Unquoted value
                value_start = i
                while i < n and line[i] not in ' \t':
                    i += 1
                value = line[value_start:i]
        
        result[key] = value
    
    return result

from typing import List, Tuple

def merge_intervals(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    if not intervals:
        return []
    
    # Create a sorted copy of intervals based on start time
    sorted_intervals = sorted(intervals)
    merged = [sorted_intervals[0]]
    
    for current_start, current_end in sorted_intervals[1:]:
        last_start, last_end = merged[-1]
        
        # Check if intervals overlap or touch
        if current_start <= last_end:
            # Merge intervals by updating the end of the last interval
            merged[-1] = (last_start, max(last_end, current_end))
        else:
            # No overlap, add the current interval to the list
            merged.append((current_start, current_end))
    
    return merged

from typing import List, Tuple

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 current_start, current_end in sorted_intervals[1:]:
        last_start, last_end = merged[-1]
        
        if current_start <= last_end:
            merged[-1] = (last_start, max(last_end, current_end))
        else:
            merged.append((current_start, current_end))
    
    return merged

from typing import List, Tuple

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 current_start, current_end in sorted_intervals[1:]:
        last_start, last_end = merged[-1]
        if current_start <= last_end:
            merged[-1] = (last_start, max(last_end, current_end))
        else:
            merged.append((current_start, current_end))
    
    return merged

from datetime import date, timedelta
from calendar import monthrange

def add_months(d: date, months: int) -> date:
    years = months // 12
    remaining_months = months % 12
    if remaining_months < 0:
        remaining_months += 12
        years -= 1

    target_year = d.year + years
    target_month = d.month + remaining_months

    while target_month > 12:
        target_month -= 12
        target_year += 1
    while target_month < 1:
        target_month += 12
        target_year -= 1

    _, last_day = monthrange(target_year, target_month)
    target_day = min(d.day, last_day)

    return date(target_year, target_month, target_day)

from datetime import date
import calendar

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

    year += months // 12
    month += months % 12

    if month <= 0:
        month += 12
        year -= 1
    elif month > 12:
        month -= 12
        year += 1

    max_day = calendar.monthrange(year, month)[1]
    day = min(day, max_day)

    return date(year, month, day)

from datetime import date, timedelta
import calendar

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

    # Calculate the target month and year
    month += months

    # Adjust year if month goes beyond 12 or below 1
    while month > 12:
        month -= 12
        year += 1
    while month < 1:
        month += 12
        year -= 1

    # Determine the last day of the target month if the original day doesn't exist
    last_day = calendar.monthrange(year, month)[1]
    new_day = min(day, last_day)

    return date(year, month, new_day)

from collections import Counter
import re

def top_k_words(text: str, k: int) -> list[tuple[str, int]]:
    words = re.findall(r"[A-Za-z']+*", text)
    filtered_words = [w for w in words if w and w.isalpha() or (w.endswith("'") and w[:-1].isalpha()) or (w.startswith("'") and w[1:].isalpha()) or (w.startswith("'") and w.endswith("'") and w[1:-1].isalpha())]
    # Simpler regex approach for ASCII letters and apostrophes
    words = re.findall(r"[A-Za-z]+(?:'[A-Za-z]+)*", text)
    counter = Counter(word.lower() for word in 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)
    word_counts = Counter(word.lower() for word in words)
    return sorted(word_counts.items(), key=lambda x: (-x[1], x[0]))[:k]

from collections import Counter

def top_k_words(text: str, k: int) -> list[tuple[str, int]]:
    words = []
    current_word = []
    
    for char in text:
        if char.isascii() and (char.isalpha() or char == "'"):
            current_word.append(char.lower())
        else:
            if current_word:
                words.append("".join(current_word))
                current_word = []
    
    if current_word:
        words.append("".join(current_word))
    
    counts = Counter(words)
    sorted_words = sorted(counts.items(), key=lambda x: (-x[1], x[0]))
    return sorted_words[:k]

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

    def _flatten(current, prefix: str):
        if isinstance(current, dict):
            if not current:
                result[prefix] = {}
                return
            for key, value in current.items():
                new_key = f"{prefix}{key}" if prefix else key
                _flatten(value, new_key)
        elif isinstance(current, list):
            if not current:
                result[prefix] = []
                return
            for index, value in enumerate(current):
                new_key = f"{prefix}{index}" if prefix else str(index)
                _flatten(value, new_key)
        else:
            result[prefix] = current

    _flatten(obj, "")
    return result

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

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

    _flatten(obj)
    return result

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

    def _flatten(current_obj: dict, prefix: str = "") -> None:
        for key, value in current_obj.items():
            new_key = f"{prefix}{key}" if prefix else key
            if isinstance(value, dict):
                _flatten(value, new_key + sep)
            elif isinstance(value, list):
                for index, item in enumerate(value):
                    if isinstance(item, dict):
                        _flatten(item, f"{new_key}{index}{sep}")
                    else:
                        result[f"{new_key}{index}"] = item
            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, tuple(sorted(kwargs.items()))) in cache:
                # Cache hit: move to end to mark as recently used
                cache.move_to_end((args, tuple(sorted(kwargs.items()))))
                return cache[(args, tuple(sorted(kwargs.items())))]
            
            # Cache miss: compute result
            result = func(*args, **kwargs)
            
            if len(cache) >= maxsize:
                # Evict least recently used (first item)
                cache.popitem(last=False)
            
            # Store new result
            cache[(args, tuple(sorted(kwargs.items())))] = result
            return result
        
        wrapper.__name__ = func.__name__
        return wrapper
    return decorator

from typing import Callable, Any, Optional
from collections import OrderedDict

def lru(maxsize: int):
    def decorator(func: Callable) -> Callable:
        cache: OrderedDict[Any, Any] = OrderedDict()
        misses: int = 0
        hits: int = 0

        def wrapper(*args: Any, **kwargs: Any) -> Any:
            nonlocal misses, hits
            # Create a hashable key from positional and keyword arguments
            key = (args, tuple(sorted(kwargs.items())))
            
            if key in cache:
                hits += 1
                # Move to end to mark as recently used
                cache.move_to_end(key)
                return cache[key]
            
            misses += 1
            
            if maxsize > 0 and len(cache) >= maxsize:
                # Evict the least recently used item (first item)
                cache.popitem(last=False)
            
            # Cache the new result
            cache[key] = func(*args, **kwargs)
            return cache[key]

        wrapper.__name__ = func.__name__
        return wrapper
    return decorator

from collections import OrderedDict
from types import FunctionType

def lru(maxsize: int):
    def decorator(func: FunctionType) -> FunctionType:
        cache = OrderedDict()
        hits = 0
        
        def wrapper(*args, **kwargs):
            nonlocal hits
            if args in cache:
                hits += 1
                # Move to end (most recently used)
                cache.move_to_end(args)
                return cache[args]
            
            if len(cache) >= maxsize:
                cache.popitem(last=False)
            
            result = func(*args, **kwargs)
            cache[args] = result
            return result
        
        wrapper.__name__ = func.__name__
        return wrapper
    
    return decorator