Implement a simple **in-memory key-value store** that processes a sequence of operations and returns the results of all reads. ## Task Implement the function: ```python def solution(operations): ... ``` The store starts **empty**. Process each operation in `operations` **in order**, then return a list containing the result of every `get` operation, in the order those `get` operations occur. ## Input `operations` is a list of tuples. Each tuple is one of the following commands: - `('put', key, value)` — store `value` under `key`. If `key` already exists, **overwrite** its value (the latest write wins). - `('get', key)` — read the value currently stored under `key`. If `key` is **not present**, the result is `None`. - `('delete', key)` — remove `key` from the store. If `key` is **not present**, do nothing (no error). Here `key` is a string and `value` is an integer. ## Output Return a **list** containing one entry per `get` operation, in the order the `get` operations were processed: - For a `get` on a key that is currently in the store, append its current value. - For a `get` on a missing key, append `None`. Only `get` operations produce output. `put` and `delete` operations modify the store but contribute nothing to the returned list. ## Examples - `[('put', 'a', 1), ('get', 'a'), ('put', 'a', 2), ('get', 'a'), ('delete', 'a'), ('get', 'a')]` → `[1, 2, None]` (read `a`, then overwrite and re-read, then delete and read the now-missing key) - `[('get', 'missing'), ('delete', 'missing'), ('get', 'missing')]` → `[None, None]` (reading and deleting an absent key are both safe) - `[]` → `[]` (no operations, no output) - `[('put', 'x', 10), ('put', 'y', 20), ('delete', 'x'), ('get', 'x'), ('get', 'y')]` → `[None, 20]` ## Constraints - `0 <= len(operations) <= 200000` - Keys are strings of length **1 to 100**. - Values are integers and are never `None`. - All operations are valid.

Implement a single-threaded, in-memory **key–value store that supports nested transactions**. The store starts empty. ## What to implement Write `solution(operations)`, where `operations` is a list of commands to apply **in order**. Each command is a sequence (tuple or list) whose **first element is the command name** (a string) and whose remaining elements are its arguments. Apply every command to the store, and **return a list** containing the results of the `get`, `commit`, and `rollback` commands **in the order they were executed**. The `put`, `delete`, and `begin` commands produce **no entry** in the result list. ## Commands | Command | Form | Effect | Appends to result? | |---------|------|--------|--------------------| | **put** | `('put', key, value)` | Set `key` to `value` (overwriting any existing value). | No | | **delete** | `('delete', key)` | Remove `key` from the store if present; otherwise do nothing. | No | | **get** | `('get', key)` | Look up `key`. | Yes — appends the current value, or **`None`** if `key` is not present. | | **begin** | `('begin',)` | Open a new transaction. Transactions may be **nested**. | No | | **commit** | `('commit',)` | Commit the **innermost** open transaction. | Yes — appends **`True`** if a transaction was open, otherwise **`False`**. | | **rollback** | `('rollback',)` | Roll back the **innermost** open transaction. | Yes — appends **`True`** if a transaction was open, otherwise **`False`**. | ## Transaction semantics - **Immediate visibility:** A `put` or `delete` is visible to every later operation right away, including later `get`s inside the same transaction. - **`rollback`** undoes only the changes made **since its matching `begin`** (the innermost open transaction), restoring every key it touched to the value it had at that `begin`. Keys created during the transaction are removed; keys deleted or overwritten are restored to their begin-time state. Operations outside the transaction are unaffected. Rolling back removes that transaction; the next-outer transaction (if any) becomes the innermost open one. - **`commit`** closes the innermost open transaction and **merges its changes into the enclosing transaction** if one exists. The changes are *not* yet made permanent in that case: a later `rollback` of the enclosing transaction will still undo them (restoring to the enclosing transaction's begin-time state). If there is no enclosing transaction, the committed changes become the persistent state of the store. - **No active transaction:** If `commit` or `rollback` runs while no transaction is open, it makes no change and appends **`False`**. ## Input / output format - **Input:** `operations` — a list of command sequences as described above. Command names are lowercase strings; `key` is a string; `value` is an integer. - **Output:** a list whose elements are, in order, the results of the `get` / `commit` / `rollback` commands: each `get` contributes its looked-up value or `None`, and each `commit` / `rollback` contributes a boolean. An empty `operations` list yields an empty result list. ## Constraints - `0 <= len(operations) <= 200000` - Maximum nested transaction depth is at most `len(operations)` - Keys are strings of length 1 to 100 - Values are integers and are never `None` - All operations are valid ## Example ``` operations = [ ('put', 'a', 1), ('begin',), ('put', 'a', 2), ('get', 'a'), # -> 2 (transaction write is visible immediately) ('begin',), ('delete', 'a'), ('get', 'a'), # -> None ('rollback',), # -> True (undo inner transaction) ('get', 'a'), # -> 2 (back to value set in outer transaction) ('commit',), # -> True (commit outer transaction) ('get', 'a'), # -> 2 ] # returns [2, None, True, 2, True, 2] ```

Implement `solution(operations)` — a **concurrent transactional key-value store** that processes a list of operations under linearizable global-lock semantics. The `operations` list is already in the **exact atomic order** in which the operations take effect, so you simply process them one by one in that order. Each operation is a tuple whose first element is the command name. Return a list of results (see **Output** below). ## Data model - There is one shared **global store** holding the latest committed key→value pairs. - Each **thread** (identified by `tid`) has its own independent stack of **nested transaction layers**. - A thread can see its own uncommitted changes, but other threads cannot see them until the thread's **outermost** transaction commits. - **Keys** are strings; **values** are integers (never `None`). ## Operations Each `op` is a tuple. `tid` is a thread id. - `('begin', tid)` — Start a new (possibly nested) transaction for that thread by pushing a fresh empty layer onto its stack. - `('put', tid, key, value)` — Set `key` to `value`. If the thread has an active transaction, the write goes into the thread's **top** (innermost) layer only; otherwise it is applied directly to the global store. - `('delete', tid, key)` — Remove `key`. If the thread has an active transaction, record the deletion in the thread's **top** layer (so the key reads as absent for that thread); otherwise remove it from the global store. - `('get', tid, key)` — Read the value of `key` for that thread (see **Reads** below). - `('commit', tid)` — Commit the thread's innermost active transaction. - `('rollback', tid)` — Discard the thread's innermost active transaction. ## Reads For `('get', tid, key)`, resolve the value as follows: 1. Scan that thread's transaction layers from **newest to oldest**. Return on the first layer that mentions `key`: if that layer recorded a `put`, return its value; if it recorded a `delete`, return `None`. 2. If no layer of the thread mentions `key`, fall back to the **current** value in the global store, or `None` if absent. This is **not** snapshot isolation. A thread reads the latest committed global value at read time, so if another thread commits a new value for a key, future reads observe that new value — **unless** the reading thread has its own `put`/`delete` on that key in an active layer (in which case its own layer wins). ## Commit semantics `('commit', tid)`: - If the thread has **no active transaction**, do nothing and record `False`. - Otherwise, pop the thread's **top** layer: - If a **parent** layer still remains, merge the popped layer's changes into the parent layer (the changes stay uncommitted, just merged one level out toward the parent). Overlapping keys overwrite the parent's pending value. - If the popped layer was the **outermost** one, apply its changes to the global store: each recorded `put` writes its value, and each recorded `delete` removes the key from the global store. - Record `True`. ## Rollback semantics `('rollback', tid)`: - If the thread has **no active transaction**, record `False`. - Otherwise, discard the thread's **top** layer (throwing away all of its pending changes) and record `True`. ## Output Return a list built by appending, in operation order, exactly one result for each `get`, `commit`, and `rollback`: - `get` → the resolved value (an integer) or `None`. - `commit` → `True` if a transaction was committed, otherwise `False`. - `rollback` → `True` if a transaction was discarded, otherwise `False`. `begin`, `put`, and `delete` produce **no** entry in the output list. ## Example Input: ``` [('put', 1, 'x', 1), ('begin', 2), ('get', 2, 'x'), ('put', 2, 'x', 5), ('get', 2, 'x'), ('get', 1, 'x'), ('commit', 2), ('get', 1, 'x')] ``` Output: `[1, 5, 1, True, 5]` - Thread 1 puts `x = 1` directly into the global store (no output). - Thread 2 begins a transaction, then reads `x` → `1` (from the global store). - Thread 2 puts `x = 5` in its own layer; its next read → `5`, but thread 1 still reads the global `1`. - Thread 2 commits (outermost) → `True`, writing `x = 5` to the global store; thread 1 now reads `5`. ## Constraints - `0 <= len(operations) <= 200000` - `1 <= number of distinct thread IDs <= 100000` - Maximum nested transaction depth per thread is at most `len(operations)`. - Keys are strings of length 1 to 100. - Values are integers and are never `None`. - All operations are valid and should be processed exactly in the given order.