Svigaruna er strengur sem samanstendur af stöfunum ( og ). Svigaruna $s_{1,2,\ldots,m}$ er skilgreind sem gild ef hún uppfyllir eitt af eftirfarandi skilyrðum:
- $s$ er tóm.
- $s_1 = $
(, $s_m = $), og $s_{2,3,\ldots,m-1}$ er gild. - Til er staðsetning $k$ ($1 \le k < m$) þannig að $s_{1,2,\ldots,k}$ er gild og $s_{k+1,k+2,\ldots,m}$ er gild.
Tvær staðsetningar $i, j$ ($1 \le i < j \le m$) í svigarununni $s_{1,2,\ldots,m}$ eru sagðar paraðar saman ef og aðeins ef bæði $s_{i,i+1,\ldots,j}$ og $s_{i+1,i+2,\ldots,j-1}$ eru gildar.
Gefin er heiltöluruna af lengd $n$, $a_1, a_2, \ldots, a_n$, þar sem tryggt er að $n$ sé slétt tala. Við búum til nýja heiltölurunu $c_1, c_2, \ldots, c_n$ með gildri svigarunu $b_1, b_2, \ldots, b_n$, þannig að $\forall 1 \le i \le n, c_i = a_{p_i}$, þar sem $p_i$ er staðsetningin sem er pöruð við staðsetningu $i$ í $b_{1,2,\ldots,n}$.
Finndu gilda svigarunu $b_{1,2,\ldots,n}$ þannig að stafrófsröð (lexicographical order) $c_{1,2,\ldots,n}$ verði sem minnst. Ef fleiri en ein lausn er til skal prenta hvaða lausn sem er.
Inntak
Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 2.5 \times 10^5$), sem gefur til kynna fjölda prófunartilvika.
Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 5 \times 10^5$), sem gefur til kynna lengd rununnar $a$, og tryggt er að $n$ sé slétt tala.
Önnur línan inniheldur $n$ heiltölur aðskildar með bilum, sem tákna $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Tryggt er að summa $n$ fer ekki yfir $5 \times 10^5$.
Úttak
Fyrir hvert prófunartilvik skal prenta línu sem inniheldur streng af lengd $n$, sem táknar $b_{1,2,\ldots,n}$.
Dæmi
Inntak 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
Úttak 1
((())) ()() (()) () ((()))()