Untamed Tree

You are given a rooted binary tree $T$. Every internal vertex of $T$ has exactly two children, a left child and a right child, and every leaf carries a label. A label is a non-empty string of lowercase English letters, and different leaves may carry the same label.

For a label $\ell$, the tree $T(\ell)$ is defined as follows:

• The leaves of $T(\ell)$ are exactly the leaves of $T$ whose label is $\ell$.
• $T(\ell)$ also contains every internal vertex of $T$ whose left subtree and right subtree both contain at least one leaf labelled $\ell$.
• Two vertices $u$ and $v$ kept in $T(\ell)$ are joined by an edge when the path between them in $T$ passes through no other kept vertex.

Write a program that, for every label appearing in $T$, determines the tree $T(\ell)$.

Each line of standard input describes exactly one vertex of $T$. The tree is given in pre-order: the first line of every (sub)tree describes its root, and if that root is an internal vertex, the description of its left subtree follows and then the description of its right subtree. A line containing a single asterisk * denotes an internal vertex. A line containing a lowercase string denotes a leaf and gives its label; the label is non-empty and consists only of the letters a to z. The total length of all labels does not exceed $1\,000\,000$ (a label is counted once for every leaf where it occurs).

Vertices are numbered by the order in which they appear in the input, starting from $1$; that is, a vertex's number equals its line number.

Print the description of every tree $T(\ell)$, one per line, with the labels $\ell$ taken in lexicographic order. Each description is written in pre-order but uses the numbers of the vertices belonging to the tree: the number of the root, followed (unless the root is a leaf) by the description of its left subtree and then of its right subtree.