Implement a `RadixCache` — a radix tree (prefix-compressed trie) that stores **sequences of integers**. In a plain trie, every node holds exactly one element, so long sequences create long chains of single-child nodes. A radix tree compresses those chains: each edge is labeled with a **non-empty list of integers**, and the tree maintains two invariants at all times: 1. **Distinct branching:** among the children of any node, no two edge labels start with the same integer. 2. **Maximal compression:** an edge label is as long as possible — a chain of nodes is only broken where sequences actually diverge (or where an inserted sequence ends). Your `RadixCache` must support: - `insert(seq)` — insert a non-empty sequence of integers into the tree. - `dump()` — return the current tree structure as a list of strings, one line per node, produced by a depth-first traversal starting from the (unlabeled) root. Each line is the string representation of that node's edge label (e.g. `[1, 2, 3]`), indented with two spaces per depth level. At every node, visit children in **ascending order of the first integer of their edge label**. ### Insertion semantics To insert a sequence, walk down from the root. At the current node, look for a child whose edge label starts with the next integer of the remaining sequence: - **No such child:** create a new child whose edge label is the entire remaining sequence, and stop. - **The remaining sequence fully consumes the edge label:** descend into that child and continue with the rest of the sequence (if nothing remains, the sequence already ends exactly at that node — the structure is unchanged). - **The remaining sequence matches only a proper prefix of the edge label (or ends inside it):** **split** the edge. Create an intermediate node whose incoming edge is the common prefix; the existing child keeps the leftover part of its original label (with all of its subtree intact); if the inserted sequence still has leftover integers, they become a second new child of the intermediate node. Duplicate inserts, and inserts of a sequence that is a prefix of an already-stored sequence, must not corrupt the structure. ### Examples **Example 1** ```python tree = RadixCache() tree.insert([10, 20]) tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5, 6]) tree.dump() ``` The tree is now: ``` Root ├── [1, 2, 3] │ └── [4, 5, 6] └── [10, 20] ``` so `dump()` returns: ``` ["[1, 2, 3]", " [4, 5, 6]", "[10, 20]"] ``` Note that `[1, 2, 3, 4, 5, 6]` shared the prefix `[1, 2, 3]` with an existing node, so only the new suffix `[4, 5, 6]` was added as a child. **Example 2** (continuing from Example 1) ```python tree.insert([1, 2, 3, 40, 50, 60, 70, 80]) tree.insert([1, 2, 3, 40, 50, 60, 700, 800]) tree.dump() ``` The first insert adds the child `[40, 50, 60, 70, 80]` under `[1, 2, 3]`. The second insert shares only the prefix `[40, 50, 60]` with that edge, so the edge is split: ``` Root ├── [1, 2, 3] │ ├── [4, 5, 6] │ └── [40, 50, 60] │ ├── [70, 80] │ └── [700, 800] └── [10, 20] ``` so `dump()` returns: ``` ["[1, 2, 3]", " [4, 5, 6]", " [40, 50, 60]", " [70, 80]", " [700, 800]", "[10, 20]"] ``` ### Constraints - $1 \le$ number of `insert` calls $\le 10^4$ - $1 \le$ length of each inserted sequence $\le 10^3$ - $0 \le$ each integer $\le 10^9$ - The total number of integers across all inserted sequences does not exceed $10^5$. - `insert` should run in $O(L)$ time for a sequence of length $L$ (excluding any cost of ordering children, which may be paid in `dump()` instead).