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.