== include(page="template/taskheader" task_id="brackets") ==

Poveste şi cerinţă...

Erai in camera ta, iti vedeai de treaba ta, treceai Trie-ul persistent in documentatia pentru Finala ACM. Deodata, bate cineva la usa. Vecinul de alaturi te roaga sa-i imprumuti doua parantezari corecte, pentru ca are niste prieteni in vizita si ar vrea sa joace un joc. Fiindca nu are o parere foarte buna despre tine, el iti ofera o definitie recursiva a corectitudinii unui sir de paranteze, in speranta ca o poti urmari:
 
- Sirul vid este corect.
- Daca sirul $A$ este corect, atunci si sirul $(A)$ este corect.
- Daca sirurile $A$ si $B$ sunt corecte, atunci si sirul $A$ concatenat cu $B$ este corect.
 
Te uiti prin camera, vezi un treap rupt in doua sub masa, un FFT cu constanta un milion scrijelit pe oglinda, in final vezi si un sir de paranteze ramas intr-o cutie de pizza.
 
Te hotarasti sa partitionezi sirul tau de paranteze (care nu e neaparat corect) in exact doua subsiruri *de lungime cat mai apropiata* (fapt aparent important pentru jocul dubios al vecinului), astfel incat ambele sa fie siruri de paranteze corecte. Vrei sa scapi cu totul de parantezele astea, asa ca nu vei lasa niciuna in cutia de pizza.

h2. Date de intrare

Fişierul de intrare $brackets.in$ ...

Fişierul de intrare $brackets.in$ va contine pe prima sa linie $T$, numarul de teste. Structura unui test este urmatoarea: pe prima linie se afla un numar $N$, reprezentand numarul de paranteze din sir. Urmatoarea linie contine un sir de paranteze de lungime $N$.

h2. Date de ieşire

În fişierul de ieşire $brackets.out$ ...

În fişierul de ieşire $brackets.out$ se vor afla multiple linii, reprezentand raspunsurile la testele corespunzatoare. Daca nu e posibil ca sirul din input sa fie partitionat in doua subsiruri de paranteze corecte, veti afisa "-1". Altfel, veti afisa numarul de paranteze din primul subsir, urmat de indicii acestui subsir. Apoi veti afisa numarul de paranteze din al doilea subsir, urmat de indicii acestui subsir. Indicii sunt numerotati de la $1$ la $N$. Intersectia celor doua multimi de indici trebuie sa fie vida, iar reuniunea celor doua multimi trebuie sa fie egala cu ${1, 2, ..., N}$. Ambele multimi de indici trebuie afisate in ordine *crescatoare*.

h2. Restricţii
* $1 ≤ T ≤ 100$
* $1 ≤ N ≤ 10.000$

* $Daca exista mai multe solutii, o vei accepta fericit pe oricare dintre acestea.$

h2. Exemplu

-1
|

h3. Explicaţie
 
...

In primul test poti partitiona cu succes sirul de paranteze in doua subsiruri corecte de paranteze de aceeasi lungime. Excelent.
In al doilea caz nu poti partitiona sirul in doua subsiruri corecte. Ai putea face asta daca nu-i oferi vecinului toate parantezele, dar nu vrei sa faci asta. Asa esti tu.

== include(page="template/taskfooter" task_id="brackets") ==