Задача A. Скобки

Автор:XIII командный чемпионат школьников Санкт-Петербурга по программированию   Ограничение времени:2 сек
Входной файл:brackets.in   Ограничение памяти:32 Мб
Выходной файл:brackets.out  

Условие

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

Примеры правильных скобочных последовательностей — «», "()", "((()))", "()()()", "((()())())(())". Неформально говоря, правильная скобочная последовательность — это последовательность скобок, которая может быть получена из некоторого арифметического выражения удалением из него всего, кроме скобок.

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

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

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

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

Входной файл содержит одну строку, состоящую только из круглых и квадратных скобок.

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

Выведите в выходной файл минимальную по длине правильную скобочную последовательность из круглых скобок, которую можно получить из заданной строки описанными операциями. Если решений несколько, выведите любое. Если из данной строки нельзя получить ни одной правильной скобочной последовательности, выведите в выходной файл слово Impossible.

Ограничения

Длина строки не превышает 2000 символов.

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

Входной файл (brackets.in) Выходной файл (brackets.out)
1
[)())(]()]
(()())()()
2
[]
3
[)(][]
()()
4
())
Impossible

0.040s 0.008s 15