Problem A. Auxiliary Question of the Universe

Author:ACM ICPC 2009-2010, NEERC, Northern Subregional Contest   Time limit:3 sec
Input file:auxiliary.in   Memory limit:256 Mb
Output file:auxiliary.out  

Statement

As you probably know, scientists already discovered the Ultimate question of life, the Universe, and everything, and it is «What do you get if you multiply six by nine?». Not satisfied by this, the scientists contracted a small Magrateyan company to construct a mini-computer to find out some more specific question (they named it auxiliary), which can theoretically shed more light on life, the Universe or something else.

This computer was built, but unluckily (although not unexpectedly) the result of computation was corrupted and partially lost. Finally the computer constructors managed to receive a string, which is a part of the correct question. After thorough analysis the constructors started to believe that the original result can be reconstructed from the string by adding some letters to it without the string letters being reordered or removed. Also they believe that the correct result is an arithmetic expression (as with the Ultimate question), but since the question is auxiliary, it contains no multiplication, only addition. More precisely, it should correspond to the depicted grammar.

They need your help to give just something to their clients. They ask you to reconstruct the question based on the corrupted computer answer which they managed to retrieve.

Input file format

The input file contains exactly one line — the corrupted auxiliary question. It is a non-empty string which is at most 1000 symbols long. This string contains only symbols "+", "(", ")", and "0", , "9".

Output file format

Output the reconstructed auxiliary question. It's guaranteed that there exists a correct question of less than 5000 symbols and your solution must also be shorter than that. If there is more than one solution, output any one.

Sample tests

No. Input file (auxiliary.in) Output file (auxiliary.out)
1
1+0+1)
(1+0+1)
2
2009
2009
3
)(()(
(0)+((0)+(0))

0.076s 0.008s 15