Matcom Online Grader

Para este problema, vamos a definir una expresión regular recursivamente de la siguiente manera:

1. Un solo carácter $\$$ es una expresión regular que acepta la cadena vacía.
2.  Caracteres individuales como por ejemplo 'a', 'b' y 'c' son expresiones regulares que aceptan cadenas "a", "b" y "c",
   respectivamente.
3. Si $P$ es una expresión regular, $(P)$ es también una expresión regular que acepta todas las cadenas aceptadas por P.
4. Si $P$ es una expresión regular que es un resultado directo de aplicar cualquiera de las reglas $1-4$, su iteración, denotado como $P*$, es también una expresión regular que acepta cadenas de la forma $s = u_1 u_2 \ldots u_k$ (la concatenación de cero o más cadenas) donde $k$ es cualquier entero no negativo y cada cadena $u_i$ es aceptada por $P$.
5. Si $P$ y $Q$ son expresiones regulares que son resultados directos de la aplicación de cualquiera de las reglas $1-5$, su
   concatenación, denotado simplemente como $PQ$, es también una expresión regular que acepta cadenas de la forma
   $s = uv$ (una concatenación de $u$ y $v$, cada una de las cuales puede estar vacía) donde el prefijo $u$ es aceptado
   por $P$ y el sufijo $v$ es aceptado por $Q$.
   
6. Si $P$ y $Q$ son expresiones regulares que son resultados directos de la aplicación de cualquiera de las reglas $1-6$, su
   unión, denotada como $P | Q$, es también una expresión regular que acepta ambas, cadenas aceptadas por $P$ y cadenas aceptadas por $Q$.

Las restricciones en las reglas $4-6$ son impuestas para evitar ambigüedades y priorizar operaciones: al leer una expresión regular, evalúe iteración, luego concatenación, luego unión. Los paréntesis desempeñan el papel habitual de priorizar las operaciones encerradas en ellos.

Dada una expresión regular $r$, encuentre la cadena más corta $s$ que es aceptada por esta expresión regular $r$. Si hay varias cadenas de este tipo imprima la menor en orden lexicográfico.

Input

Output

Sample test(s)