题目描述

世界闻名的物理学家 Juraj 最近发现了一种新的基本粒子——括号子（parenthesision）。括号子可以有开（（）或关（））两种状态。使用 Juraj 自制的粒子加速器，他创造了 $t$ 个由 $n$ 个括号子组成的叠加态序列。这 $t$ 个序列中的 $n$ 个括号子都是两个不同的位置和（不必不同的）状态的叠加态。如果序列被观测的话，括号子的波函数就将坍缩，每个括号子的位置和状态就是确定的了。Juraj 想知道这些括号子是否可以坍缩为一个合法的括号序列。

Juraj M. 博士知道这些革命性的且完全有科学依据的粒子的量子物理学已经超出了 COCI 的参赛者的知识范围，所以他提供了一个正式的题面：

给你 $t$ 个长度为 $2n$ 且由左右括号构成的括号序列。每个括号都恰好是一对括号中的一个。一对中的括号可以是不同的，也可以都是左括号或右括号。Juraj 想知道是否可以在每对括号中选一个，使得最后组成的括号序列是一个合法的括号序列。此外，如果是可能的，他需要你输出如何才能获得一个合法的括号序列。一个括号序列是合法的，如果它是一个空串，或者可以写成 $(A)$ 或者 $AB$，其中 $A$ 和 $B$ 是任意的合法括号序列。

输入格式

第一行包含一个整数 $t$，表示括号序列数。接下来描述这 $t$ 个序列。

第一行包含一个整数 $n$，表示这个序列里的括号对数。

第二行包含一个长度为 $2n$ 的字符串 $z$，$z$ 只由字符 ( 和 ) 组成。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，数字 $1,2,\dots,2n$ 在其中都只出现恰好一次。

输出格式

输出 $t$ 行，第 $i$ 行输出一个 $01$ 序列，表示可能的括号选择方案。如果第 $i$ 个序列中，第 $j$ 对括号下标为 $a_j$ 的一个被选中，输出 $0$，如果是 $b_j$ 被选中，输出 $1$。如果没有合法的选择方案，输出 $-1$。

1
4
()))((()
1 2
3 5
4 6
7 8

0 1 0 1

1
4
)()()()(
1 2
3 4
5 6
7 8

1 1 0 0

1
3
(()())
1 6
2 4
3 5

-1

提示

样例解释 1：

从原序列 ()))((() 中，只有加粗的部分会留下 ()))((()，即 ()()，它是一个合法的括号序列。

数据范围：

对于 $9\%$ 的数据：$1\le n \le 10$。

对于 $9\%$ 的数据：$z[a_i]=z[b_i]$。

对于 $18\%$ 的数据：$b_i=a_i+1$。

对于 $100\%$ 的数据：$1\le t \le 10^5,\sum n\le10^5,1\le n \le 10^5 ,1\le a_i \le b_i \le 2\times n$。

本题分值与 COCI 2021-2022#6 分值相同，满分 $110$ 分。