As children, David and Henry used to play "who can name the biggest number?"
Henry: "_Twenty!_"
David: "_Nine thousand!_"
Henry: "_A million trillion!_"
David: "_A googolplex squared!_"
Henry: "_Infinity!_"
Determined to win, David takes the game to the next level: "_Infinity plus one!_"
Lucca, passing by, objects: "_How can you count to infinity, let alone past it?_"
To give his winning move a mathematical basis, David invokes an ordered set $cal(S)$. Only two properties of $cal(S)$ are relevant:
By taking one smallest element at a time, David identifies numbers with elements of $cal(S)$:
By naming elements in this way, David can get all the natural numbers $NN = {0, 1, 2, \\dots} subsetneq cal(S)$.
In order to go beyond, he defines $infinity = min (cal(S) backslash NN)$. To get a "number" that's even bigger than $infinity$, he chooses $min (cal(S) backslash (NN union {infinity}))$.
To make this idea general, David represents a "number" by a counting program P, which takes as input a (countable, possibly infinite) subset $T subsetneq cal(S)$. Its output, denoted by P($T$), satisfies $T subset.eq "P"(T) subsetneq cal(S)$. Counting programs belong to a context-free language:
Let $T_1 = "P"_1 (emptyset)$ and $T_2 = "P"_2 (emptyset)$ be the subsets constructed by the counting programs $"P"_1$ and $"P"_2$, respectively. The following conditions are equivalent, and when they hold we'll say that $"P"_1 < "P"_2$:
Thanks to his general definition, David can be mathematically precise about what he means by "infinity plus one": he means the program [+]+, which constructs the subset ([+]+)$(emptyset) = NN union {infinity}$.
To decide who won their game, the children need you to compare numbers that are described by counting programs. Given a list of $M$ counting programs, sort them from smallest to biggest.
The first line contains an integer $M$ $(M <= 100)$.
Line $i + 1$ contains a string $"P"_i$ $(1 <= | "P"_i | <= 100)$. $"P"_i$ is guaranteed to be a counting program in the described language: all characters are _+_, _[_, or _]_, and every _[_ is matched with a corresponding _]_.
Print the list of counting programs in sorted order, from smallest to biggest. Counting programs that are equal may be printed in any order.
The symbols $subset.eq$, $subsetneq$, $union$, $backslash$, $emptyset$ mean "is equal to or contained in", "is strictly contained in", set union, set difference, and the empty set, respectively.
The sample numbers are all distinct; study them carefully using the definitions. Intuitively, you might think of the smallest entries as zero, one, seven, infinity, infinity plus one, and infinity times two, respectively. But don't let names fool you: the usual rules of arithmetic no longer apply!
## Input
The first line contains an integer $M$ $(M <= 100)$.Line $i + 1$ contains a string $"P"_i$ $(1 <= | "P"_i | <= 100)$. $"P"_i$ is guaranteed to be a counting program in the described language: all characters are _+_, _[_, or _]_, and every _[_ is matched with a corresponding _]_.
## Output
Print the list of counting programs in sorted order, from smallest to biggest. Counting programs that are equal may be printed in any order.
[samples]
## Note
The symbols $subset.eq$, $subsetneq$, $union$, $backslash$, $emptyset$ mean "is equal to or contained in", "is strictly contained in", set union, set difference, and the empty set, respectively.The sample numbers are all distinct; study them carefully using the definitions. Intuitively, you might think of the smallest entries as zero, one, seven, infinity, infinity plus one, and infinity times two, respectively. But don't let names fool you: the usual rules of arithmetic no longer apply!
**Definitions**
Let $\mathcal{S}$ be a totally ordered set containing $\mathbb{N} = \{0, 1, 2, \dots\}$ as a proper subset.
Define $\infty = \min(\mathcal{S} \setminus \mathbb{N})$.
A *counting program* $P$ is a string over the alphabet $\{+, [, ]\}$, with balanced brackets.
For any countable $T \subseteq \mathcal{S}$, $P(T)$ denotes the output set satisfying $T \subseteq P(T) \subseteq \mathcal{S}$.
Let $T_0 = \emptyset$, and define $T_P = P(\emptyset)$.
The semantics of $P$ are defined recursively:
- The program `+` corresponds to the successor function: $P(T) = T \cup \{\min(\mathcal{S} \setminus T)\}$.
- The program `[P₁ P₂ ... Pₖ]` (for $k \geq 1$) corresponds to iterated application:
$$
P(T) = P_k(P_{k-1}(\cdots P_1(T)\cdots))
$$
where each $P_i$ is a subprogram.
Let $T_{P_1} = P_1(\emptyset)$, $T_{P_2} = P_2(\emptyset)$.
Define $P_1 < P_2$ if and only if $T_{P_1} \subsetneq T_{P_2}$.
**Constraints**
1. $1 \le M \le 100$
2. For each program $P_i$, $1 \le |P_i| \le 100$
3. Each $P_i$ is a well-formed string over $\{+, [, ]\}$ with balanced brackets
**Objective**
Given $M$ counting programs $P_1, P_2, \dots, P_M$, sort them in increasing order according to the relation $<$, i.e., by ascending $T_{P_i}$ under strict inclusion.