"""Twelve-stage science-fair planning lab. Python 3.10+, standard library only.

Public entry point: build_report(data). It validates the documented input contract.
The smaller functions are learning steps and expect already validated arguments.
Run this file to print the worked example from guided-practice/math.md.
"""

from bisect import bisect_right
from functools import reduce
from math import gcd
import json


MOD = 1_000_000_007


def badge_summary(batch_id):
    """00: preserve leading zeroes; scan decimal digits without a huge int."""
    total = sum(ord(char) - ord("0") for char in batch_id)
    return {"digits": len(batch_id), "digit_sum": total,
            "even": (ord(batch_id[-1]) - ord("0")) % 2 == 0}


def packing_unit(demand):
    """01: largest equal-size bundle that divides every day's demand."""
    return reduce(gcd, demand)


def registration_code(batch_id, volunteer_count):
    """02: decimal remainder followed by binary modular exponentiation.

    This is a reproducible exercise code, NOT a secure password or unique ID.
    """
    base = 0
    for char in batch_id:
        base = (base * 10 + ord(char) - ord("0")) % MOD
    result = 1
    exponent = volunteer_count
    while exponent:
        if exponent & 1:
            result = result * base % MOD
        base = base * base % MOD
        exponent //= 2
    return result


def team_count(n, k):
    """03: exact n choose k, then reduce; order inside a team is irrelevant."""
    k = min(k, n - k)
    count = 1
    for i in range(1, k + 1):
        count = count * (n - k + i) // i
    return count % MOD


def skills_report(masks, required):
    """04: check the whole volunteer pool, not every possible k-person team."""
    available = 0
    for mask in masks:
        available |= mask
    missing = required & ~available
    return {"available_mask": available, "missing_mask": missing,
            "ready": missing == 0}


def demand_report(base, updates, queries):
    """05: half-open [left, right) range additions and range sums."""
    difference = [0] * (len(base) + 1)
    for left, right, extra in updates:
        difference[left] += extra
        difference[right] -= extra
    running = 0
    demand = []
    prefix = [0]
    for index, value in enumerate(base):
        running += difference[index]
        demand.append(value + running)
        prefix.append(prefix[-1] + demand[-1])
    return {"daily": demand, "total": prefix[-1],
            "range_totals": [prefix[right] - prefix[left]
                             for left, right in queries]}


def shortest_busy_window(demand, target):
    """06: minimum positive length with sum >= target; zero means impossible."""
    left = 0
    running = 0
    best = len(demand) + 1
    for right, value in enumerate(demand):
        running += value
        while running >= target:
            best = min(best, right - left + 1)
            running -= demand[left]
            left += 1
    return 0 if best > len(demand) else best


def delivery_capacity(demand, days):
    """07: retain order, do not split a day's batch, use at most `days` trips."""
    def feasible(capacity):
        trips, load = 1, 0
        for batch in demand:
            if load + batch > capacity:
                trips += 1
                load = 0
            load += batch
        return trips <= days

    low, high = max(demand), sum(demand)
    while low < high:
        middle = (low + high) // 2
        if feasible(middle):
            high = middle
        else:
            low = middle + 1
    return low


def choose_sessions(intervals):
    """08: maximum number of non-overlapping [start, finish) sessions.

    Return original zero-based indices in chosen time order. For deterministic
    ties, sort by finish, start, then original index.
    """
    chosen = []
    finish = -1
    for index, (start, end) in sorted(enumerate(intervals),
                                     key=lambda item: (item[1][1], item[1][0], item[0])):
        if start >= finish:
            chosen.append(index)
            finish = end
    return chosen


def booth_area2(points):
    """09: doubled area of the convex hull; no floating-point rounding."""
    points = sorted(set(map(tuple, points)))
    if len(points) < 3:
        return 0

    def cross(a, b, c):
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

    lower = []
    for point in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], point) <= 0:
            lower.pop()
        lower.append(point)
    upper = []
    for point in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], point) <= 0:
            upper.pop()
        upper.append(point)
    hull = lower[:-1] + upper[:-1]
    return abs(sum(a[0] * b[1] - a[1] * b[0]
                   for a, b in zip(hull, hull[1:] + hull[:1])))


def _extended_gcd(a, b):
    old_r, r, old_s, s, old_t, t = a, b, 1, 0, 0, 1
    while r:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    return old_r, old_s, old_t


def synchronized_launch(congruences, earliest):
    """10: generalized CRT, including non-coprime periods.

    Each pair (remainder, period) requires launch % period == remainder.
    Return the first solution >= earliest, or None if schedules conflict.
    An empty list imposes no schedule restriction.
    """
    residue, period = 0, 1
    for remainder, modulus in congruences:
        divisor, inverse_coefficient, _ = _extended_gcd(period, modulus)
        difference = remainder - residue
        if difference % divisor:
            return None
        reduced_modulus = modulus // divisor
        multiplier = (difference // divisor * inverse_coefficient) % reduced_modulus
        residue += period * multiplier
        period *= reduced_modulus
        residue %= period
    if residue < earliest:
        residue += (earliest - residue + period - 1) // period * period
    return residue


def equipment_budget(costs, budget):
    """11: greatest subset total <= budget, using meet in the middle.

    Return both the total and an actual list of original item indices.
    Equal totals may choose any valid subset; the empty subset is allowed.
    """
    def halves(values):
        result = [(0, 0)]
        for index, cost in enumerate(values):
            result += [(total + cost, mask | (1 << index))
                       for total, mask in result if total + cost <= budget]
        return result

    middle = len(costs) // 2
    left = halves(costs[:middle])
    right = sorted(halves(costs[middle:]))
    right_totals = [total for total, _ in right]
    best, left_mask, right_mask = 0, 0, 0
    for total, mask in left:
        index = bisect_right(right_totals, budget - total) - 1
        other, other_mask = right[index]
        if total + other > best:
            best, left_mask, right_mask = total + other, mask, other_mask
    indices = [i for i in range(middle) if left_mask & (1 << i)]
    indices += [middle + i for i in range(len(costs) - middle) if right_mask & (1 << i)]
    return {"spent": best, "remaining": budget - best, "indices": indices}


def _integer(value, low, high, name):
    if type(value) is not int or not low <= value <= high:
        raise ValueError(f"{name} must be an integer in [{low}, {high}]")


def _sequence(value, low, high, name):
    if not isinstance(value, (list, tuple)) or not low <= len(value) <= high:
        raise ValueError(f"{name} must contain {low}..{high} items")


def _validate(data):
    required = {"batch_id", "volunteer_masks", "team_size", "required_mask", "base_demand",
                "updates", "queries", "window_target", "shipping_days", "sessions",
                "booths", "gate_cycles", "earliest_launch", "equipment_costs", "budget"}
    if not isinstance(data, dict) or set(data) != required:
        raise ValueError("input must contain exactly the documented fields")
    batch = data["batch_id"]
    if not isinstance(batch, str) or not 1 <= len(batch) <= 1000 or any(c not in "0123456789" for c in batch):
        raise ValueError("batch_id must contain 1..1000 ASCII decimal digits")
    masks = data["volunteer_masks"]
    _sequence(masks, 1, 2000, "volunteer_masks")
    for mask in masks:
        _integer(mask, 0, (1 << 20) - 1, "volunteer mask")
    _integer(data["required_mask"], 0, (1 << 20) - 1, "required_mask")
    _integer(data["team_size"], 0, len(masks), "team_size")
    base = data["base_demand"]
    _sequence(base, 1, 2000, "base_demand")
    for value in base:
        _integer(value, 1, 10**6, "base demand")
    for key, width in (("updates", 3), ("queries", 2)):
        _sequence(data[key], 0, 2000, key)
        for item in data[key]:
            _sequence(item, width, width, key)
            left, right = item[:2]
            _integer(left, 0, len(base) - 1, "left")
            _integer(right, left + 1, len(base), "right")
            if width == 3:
                _integer(item[2], 0, 10**6, "extra demand")
    _integer(data["window_target"], 1, 10**15, "window_target")
    _integer(data["shipping_days"], 1, len(base), "shipping_days")
    _sequence(data["sessions"], 0, 2000, "sessions")
    for interval in data["sessions"]:
        _sequence(interval, 2, 2, "session")
        _integer(interval[0], 0, 10**6 - 1, "session start")
        _integer(interval[1], interval[0] + 1, 10**6, "session end")
    _sequence(data["booths"], 0, 2000, "booths")
    for point in data["booths"]:
        _sequence(point, 2, 2, "booth coordinate")
        for coordinate in point:
            _integer(coordinate, -10**6, 10**6, "coordinate")
    _sequence(data["gate_cycles"], 0, 8, "gate_cycles")
    for cycle in data["gate_cycles"]:
        _sequence(cycle, 2, 2, "gate cycle")
        _integer(cycle[1], 1, 1000, "period")
        _integer(cycle[0], 0, cycle[1] - 1, "remainder")
    _integer(data["earliest_launch"], 0, 10**12, "earliest_launch")
    _sequence(data["equipment_costs"], 0, 32, "equipment_costs")
    for cost in data["equipment_costs"]:
        _integer(cost, 0, 10**9, "equipment cost")
    _integer(data["budget"], 0, 10**9, "budget")


def build_report(data):
    """Produce all twelve stage results and a combined dispatch decision.

    `can_dispatch` means required skills exist in the complete volunteer pool,
    the booth hull has positive area, and all gate schedules can agree.
    It does not guarantee that EVERY counted team has all required skills.
    """
    _validate(data)
    demand = demand_report(data["base_demand"], data["updates"], data["queries"])
    skills = skills_report(data["volunteer_masks"], data["required_mask"])
    area2 = booth_area2(data["booths"])
    launch = synchronized_launch(data["gate_cycles"], data["earliest_launch"])
    return {
        "badge": badge_summary(data["batch_id"]),
        "packing_unit": packing_unit(demand["daily"]),
        "registration_code": registration_code(data["batch_id"], len(data["volunteer_masks"])),
        "team_count_mod": team_count(len(data["volunteer_masks"]), data["team_size"]),
        "skills": skills,
        "demand": demand,
        "shortest_busy_window": shortest_busy_window(demand["daily"], data["window_target"]),
        "delivery_capacity": delivery_capacity(demand["daily"], data["shipping_days"]),
        "session_indices": choose_sessions(data["sessions"]),
        "booth_area2": area2,
        "launch_time": launch,
        "equipment": equipment_budget(data["equipment_costs"], data["budget"]),
        "can_dispatch": skills["ready"] and area2 > 0 and launch is not None,
    }


EXAMPLE = {
    "batch_id": "1204",
    "volunteer_masks": [1, 2, 3, 4], "required_mask": 7, "team_size": 2,
    "base_demand": [2, 4, 2, 6], "updates": [[1, 3, 2]],
    "queries": [[0, 2], [1, 4]], "window_target": 10, "shipping_days": 2,
    "sessions": [[0, 2], [1, 3], [2, 4], [4, 5]],
    "booths": [[0, 0], [4, 0], [4, 3], [0, 3], [2, 1]],
    "gate_cycles": [[2, 4], [4, 6]], "earliest_launch": 11,
    "equipment_costs": [6, 4, 7, 3], "budget": 11,
}


if __name__ == "__main__":
    print(json.dumps(build_report(EXAMPLE), indent=2))