Sinulle annetaan merkkijono, jonka jokainen merkki on sulkumerkki tai kysymysmerkki. Tehtäväsi on korvata jokainen kysymysmerkki sulkumerkillä niin, että tuloksena on oikein muodostettu sulkulauseke.

Sulkulauseke on oikein muodostettu, jos se vastaa kelvollisen matemaattisen lausekkeen sulutusta. Esimerkiksi (), (()) ja (())() ovat oikein muodostettuja sulkulausekkeita.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on n merkkiä. Jokainen merkki on sulkumerkki tai kysymysmerkki.

Tuloste

Tulosta jokin oikein muodostettu sulkulauseke. Voit tulostaa minkä tahansa kelvollisen ratkaisun. Jos mitään ratkaisua ei ole olemassa, tulosta IMPOSSIBLE.

Esimerkki 1

Syöte:

(??)(?

Tuloste:

(())()

Esimerkki 2

Syöte:

(??((?

Tuloste:

IMPOSSIBLE

Osatehtävä 1 (20 pistettä)

• 1 \le n \le 10

Osatehtävä 2 (30 pistettä)

• 1 \le n \le 100

Osatehtävä 3 (50 pistettä)

• 1 \le n \le 10^5