Brackets sequence#1087
Define a correct bracket expression as follows:
The empty expression is correct.
If expression S is correct, then S and S are also correct.
If expressions A and B are correct, then the expression AB is also correct.
A sequence consisting of the characters (, ), [, and ] is given. Find the shortest correct bracket expression in which the given sequence is a subsequence, that is, such that some characters (possibly none) can be deleted from it to obtain the original sequence, without changing the order of the remaining characters.
The first line contains the characters (, ), [, and ] without spaces. The given sequence contains at most brackets.
Print the required bracket sequence without spaces.
Example 1