"""Decode nested job batches, execute FIFO, report rolling duration maxima."""
import re
from collections import deque


def decode_jobs(program, limit=10000):
    """Grammar: sequence := (LABEL:positive_integer | count[sequence])*.

    Whitespace is optional between tokens; labels contain ASCII letters only.
    Counts are positive, nesting <= 100, and every expanded frame is <= limit.
    """
    if not isinstance(limit, int) or limit < 1:
        raise ValueError("limit must be positive")
    tokens, position = [], 0
    pattern = re.compile(r"\s*(\d+|[A-Za-z]+|[\[\]:])")
    while position < len(program):
        if program[position].isspace():
            position += 1
            continue
        match = pattern.match(program, position)
        if match is None:
            raise ValueError("invalid token")
        tokens.append(match.group(1)); position = match.end()
    frames, jobs, i = [], [], 0
    while i < len(tokens):
        token = tokens[i]
        if token.isdigit():
            count = int(token)
            if count < 1 or i + 1 >= len(tokens) or tokens[i + 1] != "[" or len(frames) >= 100:
                raise ValueError("invalid repetition or nesting too deep")
            frames.append((jobs, count)); jobs = []; i += 2
        elif token == "]":
            if not frames or not jobs:
                raise ValueError("unmatched or empty batch")
            outer, count = frames.pop()
            if len(outer) + len(jobs) * count > limit:
                raise ValueError("expanded job limit exceeded")
            outer.extend(jobs * count)
            jobs = outer; i += 1
        elif token.isalpha():
            if i + 2 >= len(tokens) or tokens[i + 1] != ":" or not tokens[i + 2].isdigit():
                raise ValueError("job requires LABEL:duration")
            duration = int(tokens[i + 2])
            if duration < 1 or len(jobs) >= limit:
                raise ValueError("invalid duration or expanded job limit exceeded")
            jobs.append((token, duration)); i += 3
        else:
            raise ValueError("unexpected token")
    if frames:
        raise ValueError("unclosed batch")
    return jobs


class TwoStackQueue:
    def __init__(self):
        self.incoming, self.outgoing = [], []

    def push(self, value):
        self.incoming.append(value)

    def pop(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())
        if not self.outgoing:
            raise IndexError("empty queue")
        return self.outgoing.pop()

    def __bool__(self):
        return bool(self.incoming or self.outgoing)


def rolling_maximum(values, window):
    """Only full windows produce a value; indices distinguish equal durations."""
    if not isinstance(window, int) or window < 1:
        raise ValueError("window must be a positive integer")
    candidates, result = deque(), []
    for index, value in enumerate(values):
        while candidates and candidates[0] <= index - window:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(index)
        if index + 1 >= window:
            result.append(values[candidates[0]])
    return result


def run_batch(program, window=3, limit=10000):
    if not isinstance(window, int) or window < 1:
        raise ValueError("window must be a positive integer")
    jobs = decode_jobs(program, limit)
    queue = TwoStackQueue()
    for job in jobs:
        queue.push(job)
    completed, durations, clock = [], [], 0
    while queue:
        label, duration = queue.pop()
        clock += duration
        completed.append((label, clock))
        durations.append(duration)
    return {"completed": completed, "rolling_max": rolling_maximum(durations, window)}