متتالية الأقواس هي سلسلة مكونة من المحرفين ( و ). تُعرَّف متتالية الأقواس $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
((())) ()() (()) () ((()))()