En parentesföljd är en sträng som består av tecknen ( och ). En parentesföljd $s_{1,2,\ldots,m}$ definieras som giltig om den uppfyller ett av följande villkor:
- $s$ är tom.
- $s_1 = $
(, $s_m = $), och $s_{2,3,\ldots,m-1}$ är giltig. - Det finns en position $k$ ($1 \le k < m$) sådan att $s_{1,2,\ldots,k}$ är giltig och $s_{k+1,k+2,\ldots,m}$ är giltig.
Två positioner $i, j$ ($1 \le i < j \le m$) i parentesföljden $s_{1,2,\ldots,m}$ sägs vara matchade om och endast om både $s_{i,i+1,\ldots,j}$ och $s_{i+1,i+2,\ldots,j-1}$ är giltiga.
Givet en heltalsföljd av längd $n$, $a_1, a_2, \ldots, a_n$, där $n$ garanteras vara jämnt. Vi konstruerar en ny heltalsföljd $c_1, c_2, \ldots, c_n$ genom en giltig parentesföljd $b_1, b_2, \ldots, b_n$, sådan att $\forall 1 \le i \le n, c_i = a_{p_i}$, där $p_i$ är positionen som är matchad med position $i$ i $b_{1,2,\ldots,n}$.
Hitta en giltig parentesföljd $b_{1,2,\ldots,n}$ sådan att den lexikografiska ordningen av $c_{1,2,\ldots,n}$ minimeras. Om det finns flera lösningar, skriv ut vilken som helst av dem.
Indata
Den första raden innehåller ett heltal $T$ ($1 \le T \le 2.5 \times 10^5$), som anger antalet testfall.
För varje testfall:
Den första raden innehåller ett heltal $n$ ($1 \le n \le 5 \times 10^5$), som anger längden på följden $a$, och det garanteras att $n$ är jämnt.
Den andra raden innehåller $n$ blankstegsseparerade heltal, som representerar $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Det garanteras att summan av $n$ inte överstiger $5 \times 10^5$.
Utdata
För varje testfall, skriv ut en rad som innehåller en sträng av längd $n$, som representerar $b_{1,2,\ldots,n}$.
Exempel
Indata 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
Utdata 1
((())) ()() (()) () ((()))()