世界著名的物理学家 Juraj 最近发现了一种新型基本粒子——括号子（parenthesision）。一个括号子可以处于开状态 ( 或闭状态 )。利用他自制的粒子加速器，Juraj 创造了 $t$ 个由 $n$ 个括号子叠加态组成的序列。在每个序列中，这 $n$ 个括号子都处于两个不同位置和（不一定相同的）状态的叠加态中。如果对序列进行观测，括号子的波函数就会坍缩，每个括号子最终会落入其可能的位置和状态之一。Juraj 想知道，这些括号子是否有可能坍缩成一个合法的括号序列？

Juraj 博士深知，这些具有革命性且完全有科学依据的粒子的量子物理学原理对于普通的 COCI 参赛者来说太难理解了，因此他提供了一个形式化的任务描述：

给你 $t$ 个长度为 $2n$ 的由开括号和闭括号组成的序列。每个括号都恰好属于一个括号对。同一个括号对中的两个括号可以是不同的、都是开括号、或都是闭括号。Juraj 想知道，是否可以从每个括号对中恰好选择一个括号，使得选出的括号按原序列中的相对顺序排列后，组成一个合法的括号序列。此外，如果可行，他希望你输出应该选择哪些括号以获得合法的括号序列。一个括号序列是合法的，当且仅当它是空序列，或者可以写成 (A) 或 AB 的形式，其中 A 和 B 是任意合法的括号序列。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100\,000$)，表示括号序列的数量。接下来是 $t$ 组序列的描述。

每组序列描述的第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示序列中括号对的数量。

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

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le 2n$)，表示第 $i$ 个括号对中两个括号在字符串 $z$ 中的下标（从 1 开始）。每个数字 $1, 2, \dots, 2n$ 在这 $n$ 行中恰好出现一次。

所有测试数据的 $n$ 之和不超过 $100\,000$。

输出格式

对于每组序列，输出一行。如果存在合法的括号序列，输出一个由 $0$ 和 $1$ 组成的空格分隔的序列，表示一种可能的括号选择方案。如果选择了第 $j$ 对括号中下标为 $a_j$ 的括号，则输出 0；如果选择了下标为 $b_j$ 的括号，则输出 1。如果不存在合法的括号序列，则输出 -1。

子任务

样例

输入 1

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

输出 1

0 1 0 1

输入 2

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

输出 2

1 1 0 0

输入 3

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

输出 3

-1

说明

样例 1 说明

在原始序列 ()))((() 中，只有加粗的括号会被保留：( ) ) ) ( ( ( )。即 ()()，这是一个合法的括号序列。

样例 2 说明

在原始序列 )()()()( 中，只有加粗的括号会被保留：) ( ) ( ) ( ) (。即 (())，这是一个合法的括号序列。