Ciąg nawiasowy to napis złożony ze znaków ( oraz ). Ciąg nawiasowy $s_{1,2,\ldots,m}$ nazywamy poprawnym, jeśli spełnia jeden z poniższych warunków:
- $s$ jest pusty.
- $s_1 = $
(, $s_m = $)oraz $s_{2,3,\ldots,m-1}$ jest poprawny. - Istnieje pozycja $k$ ($1 \le k < m$) taka, że $s_{1,2,\ldots,k}$ jest poprawny oraz $s_{k+1,k+2,\ldots,m}$ jest poprawny.
Mówimy, że dwie pozycje $i, j$ ($1 \le i < j \le m$) w ciągu nawiasowym $s_{1,2,\ldots,m}$ są dopasowane wtedy i tylko wtedy, gdy zarówno $s_{i,i+1,\ldots,j}$, jak i $s_{i+1,i+2,\ldots,j-1}$ są poprawne.
Dany jest ciąg liczb całkowitych o długości $n$: $a_1, a_2, \ldots, a_n$, gdzie $n$ jest gwarantowanie parzyste. Konstruujemy nowy ciąg liczb całkowitych $c_1, c_2, \ldots, c_n$ za pomocą poprawnego ciągu nawiasowego $b_1, b_2, \ldots, b_n$ w taki sposób, że $\forall 1 \le i \le n, c_i = a_{p_i}$, gdzie $p_i$ jest pozycją dopasowaną do pozycji $i$ w $b_{1,2,\ldots,n}$.
Znajdź poprawny ciąg nawiasowy $b_{1,2,\ldots,n}$, dla którego porządek leksykograficzny ciągu $c_{1,2,\ldots,n}$ jest najmniejszy. Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 2.5 \times 10^5$), oznaczającą liczbę przypadków testowych.
Dla każdego przypadku testowego:
Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^5$), oznaczającą długość ciągu $a$; gwarantowane jest, że $n$ jest parzyste.
Drugi wiersz zawiera $n$ oddzielonych spacjami liczb całkowitych, oznaczających $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Gwarantowane jest, że suma $n$ nie przekracza $5 \times 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz wiersz zawierający napis o długości $n$, oznaczający $b_{1,2,\ldots,n}$.
Przykład
Wejście 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
Wyjście 1
((())) ()() (()) () ((()))()