403393: GYM101149 H Streets of Working Lanterns

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Streets of Working Lanternstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Policeman Anatoliy monitors a lair of unorganized criminal group spreading prohibited Asian drawings. The lair has only one entrance, which is also an exit. When someone enters into the lair, Anatoliy writes an opening round bracket in his notepad, and when someone comes out, he writes a closing round bracket.

Long surveillance provokes an appetite, so Anatoliy has to eat donuts not to starve to death. Unfortunately, after the surveillance had ended, Anatoliy discovered a lot of greasy stains left by donuts in his notepad, and they prevent to understand which brackets are opening or closing. He doesn't want his boss to shout on him, so he must restore his records. He ensured that the lair of criminals was empty before he started the surveillance and after he ended it.

Input

The input contains a single string of length no more than 5·105. This string consists of characters «(», «)» and «?». Character «(» means that someone entered into the lair, character «)» means that someone came out of it, and character «?» means that there is a greasy stain on this place, and it's impossible to determine which of the other two characters was there initially.

Output

Output a recovered string consisting of characters «(» and «)» only, so that Anatoliy really could write it in his notepad. If there are many suitable strings, output any of them. If Anatoliy messed up something and his records contained mistakes, output «Impossible», without quotes.

ExamplesInput
(?(?))
Output
()(())
Input
()
Output
()
Input
?(
Output
Impossible

加入题单

上一题 下一题 算法标签: