סדרת סוגריים היא מחרוזת המורכבת מהתווים ( ו-). סדרת סוגריים $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
((())) ()() (()) () ((()))()