{"problem":{"name":"G. Infinity Plus One","description":{"content":"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: \"_","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10236G"},"statements":[{"statement_type":"Markdown","content":"As children, David and Henry used to play \"who can name the biggest number?\"\n\nHenry: \"_Twenty!_\"\n\nDavid: \"_Nine thousand!_\"\n\nHenry: \"_A million trillion!_\"\n\nDavid: \"_A googolplex squared!_\"\n\nHenry: \"_Infinity!_\"\n\nDetermined to win, David takes the game to the next level: \"_Infinity plus one!_\"\n\nLucca, passing by, objects: \"_How can you count to infinity, let alone past it?_\"\n\nTo give his winning move a mathematical basis, David invokes an ordered set $cal(S)$. Only two properties of $cal(S)$ are relevant:\n\nBy taking one smallest element at a time, David identifies numbers with elements of $cal(S)$:\n\nBy naming elements in this way, David can get all the natural numbers $NN = {0, 1, 2, \\\\dots} subsetneq cal(S)$.\n\nIn 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}))$.\n\nTo 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:\n\nLet $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$:\n\nThanks 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}$.\n\nTo 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.\n\nThe first line contains an integer $M$ $(M <= 100)$.\n\nLine $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 _]_.\n\nPrint the list of counting programs in sorted order, from smallest to biggest. Counting programs that are equal may be printed in any order.\n\nThe 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.\n\nThe 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!\n\n## Input\n\nThe 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 _]_.\n\n## Output\n\nPrint the list of counting programs in sorted order, from smallest to biggest. Counting programs that are equal may be printed in any order.\n\n[samples]\n\n## Note\n\nThe 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!","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $\\mathcal{S}$ be a totally ordered set containing $\\mathbb{N} = \\{0, 1, 2, \\dots\\}$ as a proper subset.  \nDefine $\\infty = \\min(\\mathcal{S} \\setminus \\mathbb{N})$.  \n\nA *counting program* $P$ is a string over the alphabet $\\{+, [, ]\\}$, with balanced brackets.  \nFor any countable $T \\subseteq \\mathcal{S}$, $P(T)$ denotes the output set satisfying $T \\subseteq P(T) \\subseteq \\mathcal{S}$.  \nLet $T_0 = \\emptyset$, and define $T_P = P(\\emptyset)$.  \n\nThe semantics of $P$ are defined recursively:  \n- The program `+` corresponds to the successor function: $P(T) = T \\cup \\{\\min(\\mathcal{S} \\setminus T)\\}$.  \n- The program `[P₁ P₂ ... Pₖ]` (for $k \\geq 1$) corresponds to iterated application:  \n  $$\n  P(T) = P_k(P_{k-1}(\\cdots P_1(T)\\cdots))\n  $$  \n  where each $P_i$ is a subprogram.  \n\nLet $T_{P_1} = P_1(\\emptyset)$, $T_{P_2} = P_2(\\emptyset)$.  \nDefine $P_1 < P_2$ if and only if $T_{P_1} \\subsetneq T_{P_2}$.  \n\n**Constraints**  \n1. $1 \\le M \\le 100$  \n2. For each program $P_i$, $1 \\le |P_i| \\le 100$  \n3. Each $P_i$ is a well-formed string over $\\{+, [, ]\\}$ with balanced brackets  \n\n**Objective**  \nGiven $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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10236G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}