Implement a Radix Cache for Integer Sequences

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

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)

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).