Sparing w Programowaniu Politechnika Poznańska, 10.03.2007

Opis

Zdefiniujmy poprawną sekwencję nawiasów w następujący sposób:

1. Pusta sekwencja jest poprawną sekwencją.
2. Jeżeli S jest poprawną sekwencją, to (S) oraz [S] są poprawnymi sekwencjami.
3. Jeżeli A i B są poprawnymi sekwencjami, to AB jest również poprawną sekwencją.

Dla przykładu, każda z poniższych sekwencji znaków jest poprawną sekwencją nawiasów:

(), [], (()), ([]), ()[], ()[()]

Natomiast poniższe sekwencje nie są poprawne:

(, [, ), )(, ([)], ([(]

Dana jest pewna sekwencja znaków '(', ')', '[', oraz ']'. Twoim zadaniem jest odnalezienie najkrótszej możliwej poprawnej sekwencji nawiasów, która zawiera sekwencję znaków podaną na wejściu jako podsekwencję. Przy czym łańcuch znaków a₁a₂...a_n jest nazywany podsekwencją łańcucha b₁b₂...b_m, jeżeli istnieją takie indeksy 1 ≤ i₁ < i₂ < ... < i_n ≤ m, że a_j=b_ij dla każdego 1 ≤ j ≤ n.

Specyfikacja wejścia

W pierszej linii znajduje się liczba D (1 ≤ D ≤ 100) określająca liczbę testów.

Każda linia wejścia zawiera jeden przypadek testowy. Test składa się najwyżej z 200 nawiasów (znaki '(', ')', '[' i ']'), które zostały umieszczone w jedej linii, bez żadnych dodatkowych znaków.

Specyfikacja wyjścia

Dla każdej linii na wejściu na wyjściu wypisz jedną linię, która powinna zawierać minimalną możliwą poprawną sekwencję zawierającą podsekwencję wejściową.

Przykład

1
([(]

()[()]