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 | |
|
| 2 | |
|
| 3 | |
|