Задача E. Скобки ≡

Условие

Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок. Последовательность называется правильной, если она может быть построена по следующим правилам:

• пустая строка является правильной скобочной последовательностью;
• если S — правильная скобочная последовательность, то (S) — тоже правильная скобочная последовательность.
• если A и B — правильные скобочные последовательности, то AB — тоже правильная скобочная последовательность.

Рассмотрим последовательность скобок, содержащую как круглые, так и квадратные скобки. Пусть разрешается выполнять следующие операции: заменить открывающуюся квадратную скобку на произвольное число открывающихся круглых и заменить закрывающуюся квадратную скобку на произвольное количество закрывающихся круглых. Разрешается при замене создавать ноль скобок, то есть просто удалять соответствующую квадратную скобку.

Требуется с использованием указанных операций получить из заданной строки минимальную по длине правильную скобочную последовательность, состоящую только из круглых скобок.

Например, из строки [)())(]()] можно получить правильную скобочную последовательность (()())()().

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

[)())(]()]

(()())()()

[]

[)(][]

()()

())

Impossible