Жақшалар тізбегі — ( және ) таңбаларынан құралған жол. $s_{1,2,\ldots,m}$ жақшалар тізбегі келесі шарттардың бірін қанағаттандырса, дұрыс деп аталады:
- $s$ бос.
- $s_1 = $
(, $s_m = $), және $s_{2,3,\ldots,m-1}$ дұрыс. - $s_{1,2,\ldots,k}$ дұрыс және $s_{k+1,k+2,\ldots,m}$ дұрыс болатындай $k$ ($1 \le k < m$) орны табылады.
$s_{1,2,\ldots,m}$ жақшалар тізбегіндегі екі $i, j$ ($1 \le i < j \le m$) орны тек $s_{i,i+1,\ldots,j}$ мен $s_{i+1,i+2,\ldots,j-1}$ екеуі де дұрыс болғанда ғана жұптасқан деп аталады.
Ұзындығы $n$ болатын $a_1, a_2, \ldots, a_n$ бүтін сандар тізбегі берілген, мұндағы $n$ жұп сан екеніне кепілдік беріледі. Біз дұрыс $b_1, b_2, \ldots, b_n$ жақшалар тізбегі арқылы $\forall 1 \le i \le n, c_i = a_{p_i}$ болатындай жаңа $c_1, c_2, \ldots, c_n$ бүтін сандар тізбегін құрамыз, мұндағы $p_i$ — $b_{1,2,\ldots,n}$ тізбегіндегі $i$ орнымен жұптасқан орын.
$c_{1,2,\ldots,n}$ тізбегінің лексикографиялық реті ең кіші болатындай дұрыс $b_{1,2,\ldots,n}$ жақшалар тізбегін табыңыз. Егер шешімдер бірнешеу болса, олардың кез келгенін шығарыңыз.
Кіріс деректері
Бірінші жолда тест жағдайларының санын білдіретін бүтін сан $T$ ($1 \le T \le 2.5 \times 10^5$) берілген.
Әрбір тест жағдайы үшін:
Бірінші жолда $a$ тізбегінің ұзындығын білдіретін бүтін сан $n$ ($1 \le n \le 5 \times 10^5$) берілген, және $n$ жұп сан екеніне кепілдік беріледі.
Екінші жолда $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) мәндерін білдіретін бос орын арқылы бөлінген $n$ бүтін сан берілген.
Барлық тест жағдайлары бойынша $n$ қосындысы $5 \times 10^5$ шамасынан аспайтынына кепілдік беріледі.
Шығыс деректері
Әрбір тест жағдайы үшін $b_{1,2,\ldots,n}$ тізбегін білдіретін ұзындығы $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
((())) ()() (()) () ((()))()