#!/usr/bin/env python3
"""Original A09 reference implementations. Python 3; no third-party dependencies.
All intervals are half-open. Core runs omit audit scans and trace snapshots by
 default. Run this file to write a deterministic, explicitly checked JSON record.
"""
from bisect import bisect_left, bisect_right, insort_right
from collections import Counter
from itertools import product
from math import isqrt
from pathlib import Path
import json
import random


def check(ok, message):
    if not ok:
        raise AssertionError(message)


def integer(x):
    return type(x) is int


def ints(values):
    values = list(values)
    if not all(integer(v) for v in values):
        raise ValueError('integer values required')
    return values


def interval(n, l, r):
    if not integer(l) or not integer(r) or not 0 <= l <= r <= n:
        raise ValueError('invalid half-open interval')


class SortedBlocks:
    """Fixed-length online point assignment and count(A[l:r] <= threshold)."""
    def __init__(self, values, block_size=None):
        self.a = ints(values)
        n = len(self.a)
        if block_size is None:
            block_size = max(1, isqrt(n))
        if not integer(block_size) or block_size < 1:
            raise ValueError('positive integer block size required')
        self.B = min(block_size, max(1, n))
        self.blocks = [sorted(self.a[i:i+self.B])
                       for i in range(0, n, self.B)]

    def assign(self, i, value):
        if not integer(i) or not 0 <= i < len(self.a) or not integer(value):
            raise ValueError('invalid assignment')
        block = self.blocks[i // self.B]
        at = bisect_left(block, self.a[i])
        del block[at]
        insort_right(block, value)
        self.a[i] = value

    def count_le(self, l, r, value):
        interval(len(self.a), l, r)
        if not integer(value):
            raise ValueError('integer threshold required')
        answer = 0
        while l < r and l % self.B:
            answer += self.a[l] <= value
            l += 1
        while l + self.B <= r:
            answer += bisect_right(self.blocks[l // self.B], value)
            l += self.B
        while l < r:
            answer += self.a[l] <= value
            l += 1
        return answer

    def audit(self):
        check(self.blocks == [sorted(self.a[i:i+self.B])
                              for i in range(0, len(self.a), self.B)],
              'sorted block invariant')


def mo_statistics(values, queries, block_size=None, *, audit=False, trace=False):
    """Return (distinct, sum of squared frequencies) in input query order.
    Queries are pairs (l,r); IDs are their input positions. No point updates.
    """
    a = ints(values)
    n = len(a)
    queries = list(queries)
    for l, r in queries:
        interval(n, l, r)
    q = len(queries)
    if block_size is None:
        block_size = max(1, min(max(1, n), n // max(1, isqrt(q))))
    if not integer(block_size) or block_size < 1:
        raise ValueError('positive integer block size required')
    B = min(block_size, max(1, n))
    answers = [(0, 0)] * q
    active = [i for i, (l, r) in enumerate(queries) if l < r]
    order = sorted(active, key=lambda i: (queries[i][0] // B, queries[i][1], i))
    # Comparison-based compression: no expected-time dictionary assumption.
    dense = [0] * n
    sigma, last = 0, None
    for v, i in sorted((v, i) for i, v in enumerate(a)):
        if sigma == 0 or v != last:
            sigma += 1
            last = v
        dense[i] = sigma - 1
    freq = [0] * sigma
    L = R = distinct = square = 0
    moves = {'add_left': 0, 'add_right': 0, 'remove_left': 0, 'remove_right': 0}
    log = []

    def change(pos, delta):
        nonlocal distinct, square
        key = dense[pos]
        old = freq[key]
        if delta == 1:
            distinct += old == 0
            square += 2 * old + 1
        else:
            check(old > 0, 'cannot remove an absent value')
            distinct -= old == 1
            square -= 2 * old - 1
        freq[key] += delta

    def inspect():
        if audit:
            ref = Counter(a[L:R])
            check(sum(freq) == R-L, 'window size')
            check(distinct == len(ref) and square == sum(v*v for v in ref.values()),
                  'window frequency statistics')
            check(all(x >= 0 for x in freq), 'negative frequency')

    for i in order:
        l, r = queries[i]
        before = (L, R)
        while L > l:
            L -= 1
            change(L, 1); moves['add_left'] += 1; inspect()
        while R < r:
            change(R, 1); R += 1
            moves['add_right'] += 1; inspect()
        while L < l:
            change(L, -1); L += 1
            moves['remove_left'] += 1; inspect()
        while R > r:
            R -= 1
            change(R, -1); moves['remove_right'] += 1; inspect()
        answers[i] = distinct, square
        if trace:
            log.append({'query_id': i, 'before': before, 'after': (L, R),
                        'distinct': distinct, 'square': square})
    return {'answers': answers, 'order': order, 'block_size': B,
            'moves': moves, 'trace': log}


class Fenwick:
    """Zero-based update; prefix(r) sums positions [0,r)."""
    def __init__(self, values):
        self.bit = [0] + list(values)
        self.n = len(values)
        for i in range(1, self.n + 1):
            j = i + (i & -i)
            if j <= self.n:
                self.bit[j] += self.bit[i]

    def add(self, i, delta):
        i += 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def prefix(self, r):
        answer = 0
        while r:
            answer += self.bit[r]
            r -= r & -r
        return answer


def cdq_dominance(updates, queries, *, audit=False, trace=False):
    """updates=(x,y,z,integer_weight); queries=(x,y,z). All coordinates integer.
    Each query sums weights of updates with all three coordinates <= it.
    Equal point records retain multiplicity; signed weights are allowed.
    """
    updates = [tuple(p) for p in updates]
    queries = [tuple(p) for p in queries]
    if any(len(p) != 4 or not all(integer(v) for v in p) for p in updates):
        raise ValueError('updates require four integers')
    if any(len(p) != 3 or not all(integer(v) for v in p) for p in queries):
        raise ValueError('queries require three integers')
    zs = []
    for z in sorted(p[2] for p in updates):
        if not zs or z != zs[-1]:
            zs.append(z)
    # (x, kind, identity, y, z, weight, rank), update kind 0 before query kind 1.
    events = [(x, 0, i, y, z, w, bisect_left(zs, z))
              for i, (x, y, z, w) in enumerate(updates)]
    events.extend((x, 1, i, y, z, 0, bisect_right(zs, z))
                  for i, (x, y, z) in enumerate(queries))
    events.sort(key=lambda p: (p[0], p[1], p[2]))
    answer = [0] * len(queries)
    bit = Fenwick([0] * len(zs))
    stats = {'nodes': 0, 'insertions': 0, 'rollbacks': 0, 'prefix_queries': 0}
    log = []

    def solve(items, begin):
        stats['nodes'] += 1
        if len(items) <= 1:
            return items
        m = len(items) // 2
        left = solve(items[:m], begin)
        right = solve(items[m:], begin+m)
        inserted = []
        j = 0
        contributions = [] if trace else None
        for query in right:  # right has already been sorted by y
            if query[1] != 1:
                continue
            while j < len(left) and left[j][3] <= query[3]:
                point = left[j]
                if point[1] == 0:
                    bit.add(point[6], point[5])
                    inserted.append(point)
                    stats['insertions'] += 1
                j += 1
            value = bit.prefix(query[6])
            stats['prefix_queries'] += 1
            answer[query[2]] += value
            if trace:
                contributions.append((query[2], value))
        for point in inserted:
            bit.add(point[6], -point[5])
            stats['rollbacks'] += 1
        if audit:
            check(not any(bit.bit), 'Fenwick must be empty after each cross sweep')
        if trace:
            log.append({'segment': [begin, begin+len(items)], 'split': begin+m,
                        'inserted_update_ids': [p[2] for p in inserted],
                        'query_contributions': contributions})
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i][3] <= right[j][3]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        merged.extend(left[i:]); merged.extend(right[j:])
        return merged

    solve(events, 0)
    return {'answers': answer, 'stats': stats, 'trace': log}


def assignment_counts(initial, operations, *, audit=False):
    """Offline reduction: set(i,value), count(l,r,threshold), preserved query IDs."""
    a = ints(initial)
    n = len(a)
    updates = [(0, i+1, v, 1) for i, v in enumerate(a)]
    queries = []
    for time, operation in enumerate(operations, 1):
        if len(operation) == 3 and operation[0] == 'set':
            _, i, value = operation
            if not integer(i) or not 0 <= i < n or not integer(value):
                raise ValueError('invalid assignment event')
            updates.extend(((time, i+1, a[i], -1), (time, i+1, value, 1)))
            a[i] = value
        elif len(operation) == 4 and operation[0] == 'count':
            _, l, r, value = operation
            interval(n, l, r)
            if not integer(value):
                raise ValueError('integer threshold required')
            queries.extend(((time, r, value), (time, l, value)))
        else:
            raise ValueError('unknown operation')
    record = cdq_dominance(updates, queries, audit=audit)
    raw = record['answers']
    return {'answers': [raw[i]-raw[i+1] for i in range(0, len(raw), 2)],
            'update_events': len(updates), 'prefix_queries': len(queries),
            'cdq_stats': record['stats']}


def parallel_binary_search(initial, increments, queries, *, audit=False, trace=False):
    """First t in 0..M with sum(initial + first t increments)[l:r] >= goal.
    increments=(index, nonnegative_delta), queries=(l,r,goal), missing is None.
    """
    a = ints(initial)
    n = len(a)
    increments = list(increments)
    queries = list(queries)
    for i, delta in increments:
        if not integer(i) or not 0 <= i < n or not integer(delta) or delta < 0:
            raise ValueError('valid index and nonnegative integer delta required')
    for l, r, goal in queries:
        interval(n, l, r)
        if not integer(goal):
            raise ValueError('integer goal required')
    M, q = len(increments), len(queries)
    lo, hi = [-1]*q, [M+1]*q
    stats = {'rounds': 0, 'replayed_updates': 0, 'predicate_checks': 0,
             'initial_cells_built': 0}
    logs = []
    while True:
        pending = [i for i in range(q) if hi[i]-lo[i] > 1]
        if not pending:
            break
        buckets = [[] for _ in range(M+1)]
        for i in pending:
            buckets[(lo[i]+hi[i])//2].append(i)
        bit = Fenwick(a)
        stats['rounds'] += 1
        stats['initial_cells_built'] += n
        row = [] if trace else None
        for t in range(M+1):
            if t:
                pos, delta = increments[t-1]
                bit.add(pos, delta)
                stats['replayed_updates'] += 1
            if audit:
                ref = a.copy()
                for pos, delta in increments[:t]:
                    ref[pos] += delta
                check([bit.prefix(j+1)-bit.prefix(j) for j in range(n)] == ref,
                      'bucket replay state')
            for i in buckets[t]:
                l, r, goal = queries[i]
                value = bit.prefix(r)-bit.prefix(l)
                good = value >= goal
                stats['predicate_checks'] += 1
                if good:
                    hi[i] = t
                else:
                    lo[i] = t
                if trace:
                    row.append({'query_id': i, 'time': t, 'sum': value,
                                'true': good, 'lo': lo[i], 'hi': hi[i]})
        if trace:
            logs.append(row)
    return {'answers': [None if h == M+1 else h for h in hi],
            'lo': lo, 'hi': hi, 'stats': stats, 'trace': logs}


def brute_statistics(a, queries):
    ans = []
    for l, r in queries:
        freq = Counter(a[l:r])
        ans.append((len(freq), sum(v*v for v in freq.values())))
    return ans


def brute_first(a, increments, queries):
    a = list(a)
    answer = [None] * len(queries)
    for t in range(len(increments)+1):
        if t:
            i, d = increments[t-1]
            a[i] += d
        for q, (l, r, goal) in enumerate(queries):
            if answer[q] is None and sum(a[l:r]) >= goal:
                answer[q] = t
    return answer


def main():
    rng = random.Random(20261009)
    counts = {'block_operations': 0, 'mo_arrays': 0, 'mo_queries': 0,
              'dominance_instances': 0, 'dominance_queries': 0,
              'assignment_programs': 0, 'assignment_queries': 0,
              'pbs_instances': 0, 'pbs_queries': 0, 'invalid_inputs': 0}
    for n in range(0, 26):
        for B in range(1, max(2, n+1)):
            a = [rng.randrange(-4, 5) for _ in range(n)]
            blocks = SortedBlocks(a, B)
            for _ in range(55):
                if n and rng.randrange(3) == 0:
                    i, v = rng.randrange(n), rng.randrange(-4, 5)
                    blocks.assign(i, v); a[i] = v; blocks.audit()
                else:
                    l, r = sorted([rng.randrange(n+1), rng.randrange(n+1)])
                    v = rng.randrange(-5, 6)
                    check(blocks.count_le(l, r, v) == sum(x <= v for x in a[l:r]),
                          ('blocks', a, B, l, r, v))
                counts['block_operations'] += 1
    for n in range(7):
        intervals = [(l, r) for l in range(n+1) for r in range(l, n+1)]
        for a in product(range(3), repeat=n):
            queries = intervals + intervals[::-1]
            expected = brute_statistics(a, queries)
            for B in sorted({1, max(1, n//2), max(1, n)}):
                record = mo_statistics(a, queries, B, audit=True)
                check(record['answers'] == expected, ('Mo', a, B))
                counts['mo_queries'] += len(queries)
            counts['mo_arrays'] += 1
    for trial in range(2200):
        updates = [(rng.randrange(-2, 3), rng.randrange(-2, 3), rng.randrange(-2, 3),
                    rng.randrange(-3, 4)) for _ in range(rng.randrange(22))]
        queries = [tuple(rng.randrange(-3, 4) for _ in range(3))
                   for _ in range(rng.randrange(20))]
        expected = [sum(w for x, y, z, w in updates if x <= a and y <= b and z <= c)
                    for a, b, c in queries]
        actual = cdq_dominance(updates, queries, audit=True)
        check(actual['answers'] == expected, ('dominance', updates, queries))
        counts['dominance_instances'] += 1
        counts['dominance_queries'] += len(queries)
    for _ in range(1500):
        n = rng.randrange(16)
        a = [rng.randrange(-3, 4) for _ in range(n)]
        blocks = SortedBlocks(a)
        ops, expected = [], []
        for t in range(rng.randrange(40)):
            if n and rng.randrange(2):
                i, v = rng.randrange(n), rng.randrange(-3, 4)
                ops.append(('set', i, v)); blocks.assign(i, v)
            else:
                l, r = sorted([rng.randrange(n+1), rng.randrange(n+1)])
                v = rng.randrange(-4, 5)
                ops.append(('count', l, r, v))
                expected.append(sum(x <= v for x in blocks.a[l:r]))
                check(blocks.count_le(l, r, v) == expected[-1], 'online vs direct')
        record = assignment_counts(a, ops, audit=True)
        check(record['answers'] == expected, ('assignment reduction', a, ops))
        counts['assignment_programs'] += 1
        counts['assignment_queries'] += len(expected)
    for _ in range(2200):
        n = rng.randrange(14)
        a = [rng.randrange(-5, 6) for _ in range(n)]
        increments = [(rng.randrange(n), rng.randrange(6)) for _ in range(rng.randrange(17))] if n else []
        queries = []
        for j in range(rng.randrange(18)):
            l, r = sorted([rng.randrange(n+1), rng.randrange(n+1)])
            queries.append((l, r, rng.randrange(-12, 35)))
        record = parallel_binary_search(a, increments, queries, audit=True)
        check(record['answers'] == brute_first(a, increments, queries), ('PBS', a, increments, queries))
        check(record['stats']['rounds'] <= (len(increments)+1).bit_length(), 'binary depth')
        counts['pbs_instances'] += 1
        counts['pbs_queries'] += len(queries)
    invalid = [lambda: SortedBlocks([1], 0), lambda: SortedBlocks([True]),
               lambda: SortedBlocks([]).assign(0, 1),
               lambda: mo_statistics([1], [(1, 0)]),
               lambda: cdq_dominance([(1, 2, 3, 0.5)], []),
               lambda: parallel_binary_search([0], [(0, -1)], [(0, 1, 1)]),
               lambda: parallel_binary_search([], [(0, 0)], []),
               lambda: assignment_counts([0], [('set', 1, 2)])]
    for f in invalid:
        try:
            f()
        except ValueError:
            counts['invalid_inputs'] += 1
        else:
            raise AssertionError('invalid input accepted')
    a = [3, 1, 3, 2, 1, 4, 2, 3]
    ops = [('count', 1, 7, 2), ('set', 2, 1), ('count', 0, 4, 1),
           ('set', 5, 1), ('count', 2, 8, 2), ('set', 2, 1), ('count', 4, 4, 99)]
    queries = [(2, 7), (0, 4), (4, 8), (1, 6), (3, 3), (0, 8), (3, 5)]
    increments = [(1, 2), (3, 3), (0, 1), (2, 4), (1, 0), (3, 2)]
    first_queries = [(0, 2, 3), (2, 4, 5), (0, 4, 0), (1, 3, 7), (0, 1, 2), (2, 2, 1)]
    equal_updates = [(0, 1, 2, 3), (0, 1, 2, -1), (1, 0, 2, 5), (0, 2, 1, 7)]
    result = {'status': 'PASS', 'checks': counts,
              'examples': {'initial': a, 'assignment_operations': ops,
                           'assignment': assignment_counts(a, ops, audit=True),
                           'mo_queries': queries, 'mo': mo_statistics(a, queries, 3, audit=True, trace=True),
                           'dominance_updates': equal_updates,
                           'dominance': cdq_dominance(equal_updates, [(0, 1, 2), (1, 2, 2)], audit=True, trace=True),
                           'pbs_initial': [0, 0, 0, 0], 'increments': increments,
                           'pbs_queries': first_queries,
                           'pbs': parallel_binary_search([0]*4, increments, first_queries, audit=True, trace=True)}}
    output = Path(__file__).with_name('algorithms-batched-range-results.json')
    output.write_text(json.dumps(result, ensure_ascii=False, indent=2)+'\n')
    print(json.dumps(result, ensure_ascii=False, indent=2))


if __name__ == '__main__':
    main()