"""Stable product sorting and exact/range queries; no third-party packages."""


def bubble_sort(items, key=lambda item: item, stats=None):
    result = list(items)
    for end in range(len(result) - 1, 0, -1):
        changed = False
        for i in range(end):
            if stats is not None:
                stats["comparisons"] += 1
            if key(result[i]) > key(result[i + 1]):
                result[i], result[i + 1] = result[i + 1], result[i]
                changed = True
        if not changed:
            break
    return result


def merge_sort(items, key=lambda item: item, stats=None):
    source = list(items)
    width = 1
    while width < len(source):
        target = []
        for start in range(0, len(source), 2 * width):
            left, right = source[start:start + width], source[start + width:start + 2 * width]
            i = j = 0
            while i < len(left) and j < len(right):
                if stats is not None:
                    stats["comparisons"] += 1
                if key(left[i]) <= key(right[j]):
                    target.append(left[i])
                    i += 1
                else:
                    target.append(right[j])
                    j += 1
            target.extend(left[i:])
            target.extend(right[j:])
        source = target
        width *= 2
    return source


def quick_sort(items, key=lambda item: item, stats=None):
    # Explicit task stack avoids Python's recursion limit on bad partitions.
    tasks = [(False, list(items))]
    result = []
    while tasks:
        emit, part = tasks.pop()
        if emit or len(part) < 2:
            result.extend(part)
            continue
        pivot = key(part[len(part) // 2])
        less, equal, greater = [], [], []
        for item in part:
            value = key(item)
            if stats is not None:
                stats["comparisons"] += 1
            if value < pivot:
                less.append(item)
            else:
                if stats is not None:
                    stats["comparisons"] += 1
                if value > pivot:
                    greater.append(item)
                else:
                    equal.append(item)
        tasks.extend([(False, greater), (True, equal), (False, less)])
    return result


def lower_bound(values, target):
    """First i with values[i] >= target; input must already be sorted."""
    low, high = 0, len(values)
    while low < high:
        middle = (low + high) // 2
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle
    return low


def upper_bound(values, target):
    """First i with values[i] > target; input must already be sorted."""
    low, high = 0, len(values)
    while low < high:
        middle = (low + high) // 2
        if values[middle] <= target:
            low = middle + 1
        else:
            high = middle
    return low


def catalog_report(products, queries, budget):
    """Products: distinct (nonempty string ID, nonnegative integer price)."""
    products, queries = list(products), list(queries)
    if len(products) > 200:
        raise ValueError("This comparison lab accepts at most 200 products")
    if type(budget) is not int or budget < 0:
        raise ValueError("budget must be a nonnegative integer")
    seen = set()
    for product in products:
        if not isinstance(product, (tuple, list)) or len(product) != 2:
            raise ValueError("products must contain (ID, price) pairs")
        name, price = product
        if not isinstance(name, str) or not name or name in seen:
            raise ValueError("product IDs must be nonempty and unique")
        if type(price) is not int or price < 0:
            raise ValueError("prices must be nonnegative integers")
        seen.add(name)
    if any(type(q) is not int or q < 0 for q in queries):
        raise ValueError("queries must be nonnegative integers")
    counts, outputs = {}, {}
    for name, algorithm in (("bubble", bubble_sort), ("merge", merge_sort), ("quick", quick_sort)):
        stats = {"comparisons": 0}
        outputs[name] = algorithm(products, key=lambda p: p[1], stats=stats)
        counts[name] = stats["comparisons"]
    if not outputs["bubble"] == outputs["merge"] == outputs["quick"]:
        raise AssertionError("sort implementations disagree")
    ordered = outputs["merge"]
    prices = [price for _, price in ordered]
    matches = []
    for target in queries:
        left, right = lower_bound(prices, target), upper_bound(prices, target)
        matches.append({"price": target, "ids": [name for name, _ in ordered[left:right]]})
    return {
        "ordered": ordered,
        "matches": matches,
        "affordable": [name for name, _ in ordered[:upper_bound(prices, budget)]],
        "comparisons": counts,
    }