Sulkuilmaisu on merkkijono, joka koostuu merkeistä ( ja ). Sulkuilmaisu $s_{1,2,\ldots,m}$ määritellään kelvolliseksi, jos se täyttää yhden seuraavista ehdoista:
- $s$ on tyhjä.
- $s_1 = $
(, $s_m = $), ja $s_{2,3,\ldots,m-1}$ on kelvollinen. - On olemassa kohta $k$ ($1 \le k < m$) siten, että $s_{1,2,\ldots,k}$ on kelvollinen ja $s_{k+1,k+2,\ldots,m}$ on kelvollinen.
Sulkuilmaisun $s_{1,2,\ldots,m}$ kahden kohdan $i, j$ ($1 \le i < j \le m$) sanotaan olevan vastinpari jos ja vain jos sekä $s_{i,i+1,\ldots,j}$ että $s_{i+1,i+2,\ldots,j-1}$ ovat kelvollisia.
Annettuna on pituutta $n$ oleva kokonaislukujono $a_1, a_2, \ldots, a_n$, missä $n$ on taatusti parillinen. Muodostamme uuden kokonaislukujonon $c_1, c_2, \ldots, c_n$ kelvollisen sulkuilmaisun $b_1, b_2, \ldots, b_n$ avulla siten, että $\forall 1 \le i \le n, c_i = a_{p_i}$, missä $p_i$ on kohdan $i$ vastinpari sulkuilmaisussa $b_{1,2,\ldots,n}$.
Etsi sellainen kelvollinen sulkuilmaisu $b_{1,2,\ldots,n}$, jolla jonon $c_{1,2,\ldots,n}$ aakkosjärjestys (leksikografinen järjestys) on mahdollisimman pieni. Jos ratkaisuja on useita, tulosta mikä tahansa niistä.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 2.5 \times 10^5$), joka ilmaisee testitapausten lukumäärän.
Jokaisessa testitapauksessa:
Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 5 \times 10^5$), joka ilmaisee jonon $a$ pituuden, ja on taattu, että $n$ on parillinen.
Toinen rivi sisältää $n$ välilyönnein erotettua kokonaislukua, jotka ilmaisevat luvut $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
On taattu, että lukujen $n$ summa ei ylitä arvoa $5 \times 10^5$.
Tuloste
Tulosta jokaista testitapausta kohden rivi, joka sisältää pituutta $n$ olevan merkkijonon, joka kuvaa sulkuilmaisua $b_{1,2,\ldots,n}$.
Esimerkit
Syöte 1
5 6 4 1 5 4 1 1 4 1 2 3 2 4 1 3 1 2 2 2 1 8 8 5 2 6 1 4 3 7
Tuloste 1
((())) ()() (()) () ((()))()