"""Guided lab: Fenwick totals plus segment-tree weakest-stock queries."""


class Fenwick:
    def __init__(self, values):
        self.tree = [0] * (len(values) + 1)
        for index, value in enumerate(values):
            self.add(index, value)

    def add(self, index, delta):
        if not 0 <= index < len(self.tree) - 1:
            raise ValueError("Fenwick index is outside the stock array")
        index += 1
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & -index

    def prefix(self, end):
        if not 0 <= end < len(self.tree):
            raise ValueError("Prefix endpoint must be between 0 and n")
        total = 0
        while end:
            total += self.tree[end]
            end -= end & -end
        return total

    def range_sum(self, left, right):
        if not 0 <= left <= right < len(self.tree):
            raise ValueError("Invalid half-open sum range")
        return self.prefix(right) - self.prefix(left)


class MinimumTree:
    def __init__(self, values):
        if not values:
            raise ValueError("A minimum tree needs at least one value")
        self.length = len(values)
        self.size = 1
        while self.size < len(values):
            self.size *= 2
        self.tree = [(float("inf"), -1)] * (2 * self.size)
        for index, value in enumerate(values):
            self.tree[self.size + index] = (value, index)
        for node in range(self.size - 1, 0, -1):
            self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])

    def set(self, index, value):
        if not 0 <= index < self.length:
            raise ValueError("Minimum-tree index is outside the stock array")
        node = self.size + index
        self.tree[node] = (value, index)
        node //= 2
        while node:
            self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])
            node //= 2

    def minimum(self, left, right):
        if not 0 <= left < right <= self.length:
            raise ValueError("Minimum query requires a nonempty range")
        left += self.size
        right += self.size
        best = (float("inf"), -1)
        while left < right:
            if left % 2:
                best = min(best, self.tree[left])
                left += 1
            if right % 2:
                right -= 1
                best = min(best, self.tree[right])
            left //= 2
            right //= 2
        return best


def inventory_report(initial, events, threshold):
    """Events: ('set', i, value), ('inspect', l, r), ('refill', l, r)."""
    if not initial or threshold < 0 or any(value < 0 for value in initial):
        raise ValueError("Stock must be nonempty and nonnegative")
    values = list(initial)
    totals, minima = Fenwick(values), MinimumTree(values)
    reports = []

    def assign(index, value):
        totals.add(index, value - values[index])
        minima.set(index, value)
        values[index] = value

    for kind, left, right in events:
        if kind == "set":
            if not 0 <= left < len(values) or right < 0:
                raise ValueError("Invalid stock assignment")
            assign(left, right)
            continue
        if kind not in ("inspect", "refill") or not 0 <= left < right <= len(values):
            raise ValueError("A query needs a nonempty half-open range [l, r)")
        minimum, index = minima.minimum(left, right)
        needed = max(0, threshold - minimum)
        reports.append({"kind": kind, "range": (left, right),
                        "total": totals.range_sum(left, right),
                        "minimum": minimum, "index": index, "needed": needed})
        if kind == "refill" and needed:
            assign(index, threshold)
    return {"reports": reports, "stock": values}