Implement a **snapshotable integer set**: a mutable set of integers from which you can take read-only snapshots, then iterate over any snapshot's contents in sorted order — even while the live set keeps changing afterward. ## What to implement Write a function `solution(operations)` that replays a sequence of operations against a single live set (initially empty) and returns a list of results. `operations` is a **list of tuples**. The first element of each tuple is the command name (a string); the remaining element, when present, is the argument. ## Operations Some operations mutate the live set and produce **no output**: - `('add', x)` — insert integer `x` into the live set. If `x` is already present, do nothing. - `('remove', x)` — remove `x` from the live set if it is present. If `x` is absent, do nothing. The remaining operations each **append one value** to the result list: - `('contains', x)` — return `True` if `x` is in the **current live set**, else `False`. This always checks the live set, never a snapshot. - `('snapshot',)` — record the current contents of the live set and return the new **snapshot id** `sid`. Snapshot ids are assigned `0, 1, 2, …` in the order snapshots are taken. A snapshot may be taken of an empty live set. - `('iterator', sid)` — create a new in-order iterator over the elements that existed in snapshot `sid`, and return the new **iterator id** `iid`. Iterator ids are assigned `0, 1, 2, …` in the order iterators are created. - `('next', iid)` — advance iterator `iid` and return its next element in **strictly increasing order**, or `None` if the iterator has already yielded every element of its snapshot. ## Snapshot and iterator semantics - A **snapshot** captures the live set exactly as it was at the moment `('snapshot',)` ran. Later `add`/`remove` operations on the live set do **not** change any existing snapshot. - An **iterator** is bound to its snapshot and is fully **isolated from later mutations**: once created, it yields exactly the elements of that snapshot in increasing order, regardless of any `add`/`remove` calls (or new snapshots) that happen afterward. - Each iterator tracks its own position. Calling `('next', iid)` repeatedly walks that snapshot's elements from smallest to largest; after the last element, every further `next` on that iterator returns `None`. - Multiple iterators (over the same or different snapshots) can be active at once, each advancing independently. ## Output Return a list containing the result of every operation that produces output, in the order those operations appear: - `contains` → `bool` - `snapshot` → `int` (the snapshot id) - `iterator` → `int` (the iterator id) - `next` → `int`, or `None` when the iterator is exhausted ## Example Given `operations`: ``` ('add', 1), ('add', 2), ('snapshot',), ('remove', 1), ('snapshot',), ('iterator', 0), ('next', 0), ('next', 0), ('next', 0), ('iterator', 1), ('next', 1), ('next', 1), ('contains', 1) ``` the result is: ``` [0, 1, 0, 1, 2, None, 1, 2, None, False] ``` - After the two adds, snapshot 0 captures `{1, 2}` (returns `0`). - `remove(1)` leaves the live set as `{2}`; snapshot 1 captures `{2}` (returns `1`). - Iterator 0 (over snapshot 0) yields `1`, then `2`, then `None`. - Iterator 1 (over snapshot 1) yields `2`, then `None`. - `contains(1)` is `False` because `1` was removed from the live set. ## Constraints - `1 <= len(operations) <= 200000` - Values are integers in the range `[-10^9, 10^9]`. - Every snapshot id and iterator id used as an argument is valid (it refers to a snapshot/iterator that was already created). - **Target complexity:** `add` / `remove` / `contains` in `O(log n)` expected, `snapshot` in `O(1)`, iterator creation in `O(log n)`, and `next` in `O(1)` amortized. > **Interview discussion note:** a full design discussion would compare copy-on-write (simple but expensive updates), versioned hash buckets (good lookups but awkward ordered iteration), and persistent balanced trees. For this coding task, aim for the persistent balanced-tree style solution. Snapshot reclamation can be handled by dropping unused snapshot roots/iterators so unreachable nodes are garbage-collected.

def solution(operations):
    import random

    rng = random.Random(0)

    class Node:
        __slots__ = ('key', 'prio', 'left', 'right')
        def __init__(self, key, prio, left=None, right=None):
            self.key = key
            self.prio = prio
            self.left = left
            self.right = right

    def contains(root, x):
        while root is not None:
            if x < root.key:
                root = root.left
            elif x > root.key:
                root = root.right
            else:
                return True
        return False

    def merge(a, b):
        if a is None:
            return b
        if b is None:
            return a
        if a.prio < b.prio:
            return Node(a.key, a.prio, a.left, merge(a.right, b))
        else:
            return Node(b.key, b.prio, merge(a, b.left), b.right)

    def split(root, key):
        # returns (< key, >= key)
        if root is None:
            return None, None
        if key <= root.key:
            l, r_left = split(root.left, key)
            return l, Node(root.key, root.prio, r_left, root.right)
        else:
            l_right, r = split(root.right, key)
            return Node(root.key, root.prio, root.left, l_right), r

    def add(root, x):
        if contains(root, x):
            return root
        left, right = split(root, x)
        node = Node(x, rng.getrandbits(64))
        return merge(merge(left, node), right)

    def remove(root, x):
        # Remove x if present (safe even if absent)
        left, mid_right = split(root, x)
        mid, right = split(mid_right, x + 1)
        return merge(left, right)

    def push_left(node, stack):
        while node is not None:
            stack.append(node)
            node = node.left

    live_root = None
    snapshots = []  # list of roots
    iterators = []  # list of stacks for in-order traversal

    out = []
    for op in operations:
        cmd = op[0]
        if cmd == 'add':
            x = op[1]
            live_root = add(live_root, x)
        elif cmd == 'remove':
            x = op[1]
            live_root = remove(live_root, x)
        elif cmd == 'contains':
            x = op[1]
            out.append(contains(live_root, x))
        elif cmd == 'snapshot':
            snapshots.append(live_root)
            out.append(len(snapshots) - 1)
        elif cmd == 'iterator':
            sid = op[1]
            root = snapshots[sid] if 0 <= sid < len(snapshots) else None
            stack = []
            push_left(root, stack)
            iterators.append(stack)
            out.append(len(iterators) - 1)
        elif cmd == 'next':
            iid = op[1]
            if 0 <= iid < len(iterators):
                stack = iterators[iid]
                if stack:
                    node = stack.pop()
                    push_left(node.right, stack)
                    out.append(node.key)
                else:
                    out.append(None)
            else:
                out.append(None)
        else:
            # Unknown command: ignore or raise; per problem, not expected
            pass

    return out