Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito ha creado su propio compactador de texto ( TextCompact ). Él se inventó un algoritmo muy básico que aprovecha al máximo los patrones que se repiten en un texto . Si su algoritmo se encuentra la cadena 'abcabcabc ' entonces lo representa como ‘ (abc)3 ’. Si TextCompact se encuentra el texto ' axyxyxyxyb ’, lo reescribe como ‘ a(xy)4b ' y adicionalmente, patrones anidados pueden ser aprovechados como el siguiente ejemplo:

Fito está muy contento y le prestó su programa a su amigo Pepe. Pepe llegó muy embullado a su casa, agarró un archivo y lo compactó, luego de un tiempo, se dio cuenta de que el algoritmo de Fito no tenía la opción inversa. Pepe le avisó a Fito, pero este no ha podido encontrar la forma de extraer la información original dado el archivo que TextCompact genera. Fito ha venido pidiéndote ayuda, él desea que dado el texto que ha producido su algoritmo, usted obtenga el texto original.

Input

Línea 1 : El texto resultante producido por TextCompact . Solamente letras en minúscula del alfabeto inglés $(a, b, …, z)$, paréntesis balanceados y dígitos (solamente después de un paréntesis cerrando, indicando la cantidad de veces que se repite la expresión dentro de los paréntesis correspondientes).

Output

Línea 1 : El texto original. Se asegura que la longitud es menor o igual a 1000.

Sample test(s)

Hints

Hint

Note que TextCompact produce el menor texto posible (incluyendo los paréntesis y dígitos). Para el ejemplo, el texto original contiene 16 caracteres y el resultado de comprimirlo 12.