ลำดับวงเล็บคือสตริงที่ประกอบด้วยอักขระ ( และ ) ลำดับวงเล็บ $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
((())) ()() (()) () ((()))()