Дужкова послідовність — це рядок, що складається з символів ( та ). Дужкова послідовність $s_{1,2,\ldots,m}$ визначається як правильна, якщо вона задовольняє одну з таких умов:
- $s$ порожня.
- $s_1 = $
(, $s_m = $), і $s_{2,3,\ldots,m-1}$ є правильною. - Існує позиція $k$ ($1 \le k < m$) така, що $s_{1,2,\ldots,k}$ є правильною і $s_{k+1,k+2,\ldots,m}$ є правильною.
Дві позиції $i, j$ ($1 \le i < j \le m$) у дужковій послідовності $s_{1,2,\ldots,m}$ називаються спареними тоді й лише тоді, коли обидві послідовності $s_{i,i+1,\ldots,j}$ та $s_{i+1,i+2,\ldots,j-1}$ є правильними.
Дано цілочисельну послідовність довжини $n$: $a_1, a_2, \ldots, a_n$, де гарантується, що $n$ є парним. Ми будуємо нову цілочисельну послідовність $c_1, c_2, \ldots, c_n$ за допомогою правильної дужкової послідовності $b_1, b_2, \ldots, b_n$ так, що $\forall 1 \le i \le n, c_i = a_{p_i}$, де $p_i$ — позиція, спарена з позицією $i$ в $b_{1,2,\ldots,n}$.
Знайдіть правильну дужкову послідовність $b_{1,2,\ldots,n}$ таку, щоб лексикографічний порядок $c_{1,2,\ldots,n}$ був мінімальним. Якщо розв'язків декілька, виведіть будь-який із них.
Вхідні дані
Перший рядок містить ціле число $T$ ($1 \le T \le 2.5 \times 10^5$), що вказує на кількість наборів вхідних даних.
Для кожного набору вхідних даних:
Перший рядок містить ціле число $n$ ($1 \le n \le 5 \times 10^5$), що вказує на довжину послідовності $a$, і гарантується, що $n$ є парним.
Другий рядок містить $n$ розділених пробілами цілих чисел, що представляють $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Гарантується, що сума $n$ не перевищує $5 \times 10^5$.
Вихідні дані
Для кожного набору вхідних даних виведіть рядок, що містить рядок довжини $n$, який представляє $b_{1,2,\ldots,n}$.
Приклади
Вхідні дані 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
Вихідні дані 1
((())) ()() (()) () ((()))()