Fişierul intrare/ieşire:	match.in, match.out	Sursă	CEOI 2016, Ziua 2
Autor	Adrian Budau	Adăugată de	Vlad Dumitru-Popescu •depevlad
Timp execuţie pe test	0.25 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Match

Vom defini o secvenţă validă de paranteze ca pe un şir de caractere care poate fi:

• Un şir vid;
• Un şir (B), unde B o secvenţă validă de paranteze.
• LR, concatenarea a două şiruri L şi R ambele fiind secvenţe valide de paranteze.

Fie B be o secvenţă validă de paranteze de lungime N. Vom defini B(i) ca a i-ulea caracter din secvenţa B. Pentru doi indici i şi j, 1 ≤ i < j ≤ N, spunem că B(i) şi B(j) formează o potrivire de paranteze dacă:

• B(i) = '(' şi B(j) = ')';
• i = j-1, sau subsecvenţa C = B(i + 1)B(i + 2) … B(j - 1) este o secvenţă validă de paranteze.

Fie S un şir de litere mici din alfabetul englez. Vom defini S(i) ca a i-ulea caracter din secvenţa S. Spunem că o secvenţă validă de paranteze B se potriveşte cu S dacă:

• B are aceeaşi lungime ca şi S;
• Pentru orice pereche de indici i şi j, i < j, dacă parantezele B(i) şi B(j) formează o potrivire, atunci S(i) = S(j).

Pentru un şir S format din N litere mici, găseşte cea mai mică, în sens lexicografic, secvenţă validă de paranteze, care se potriveşte cu S, sau scrie -1 dacă o asemenea secvenţă nu există.

Intrare

Fişierul de intrare match.in conţine un şir S din N litere mici în prima linie.

Iesire

În fişierul de ieşire match.out vei scrie un şir B din N caractere care reprezintă cea mai mica în sens lexicografic secvenţă validă de paranteze, care se potriveşte cu şirul de intrare, sau -1 dacă o asemenea secvenţă nu există.

Restrictii si Precizari:

• 2 ≤ N ≤ 100000
• Pentru testele în valoare de 10 puncte N ≤ 18.
• Pentru testele în valoare de 27 puncte N ≤ 2 000.
• Spunem că o secvenţă de paranteze A este mai mică în sens lexicografic decât secvenţa de paranteze B dacă există un indice i, 1 ≤ i ≤ N, astfel încât Aj = Bj pentru fiecare j < i, şi A(i) < B(i).
• Caracterul '(' se consideră lexicografic mai mic decât caracterul ')'.

Exemplu

Cum se trimit solutii?