Problem Description

Renowned physicist Juraj has recently discovered a new elementary particle—the parenthesision. A parenthesision can be in one of two states: open (() or closed ()). Using Juraj's homemade particle accelerator, he has created $t$ sequences of superposition states, each consisting of $n$ parenthesisions. In these $t$ sequences, the $n$ parenthesisions are in superposition states of two different positions and (not necessarily different) states. If the sequence is observed, the wave function of the parenthesisions will collapse, and each parenthesision's position and state will be determined. Juraj wants to know if these parenthesisions can collapse into a valid bracket sequence.

Dr. Juraj M. knows that the quantum physics of these revolutionary and entirely scientifically grounded particles is beyond the knowledge scope of COCI participants, so he provides a formal problem statement:

You are given $t$ bracket sequences of length $2n$ consisting of left and right brackets. Each bracket is exactly one of a pair. The brackets in a pair can be different or both left or right brackets. Juraj wants to know if it is possible to choose one bracket from each pair to form a valid bracket sequence. Additionally, if it is possible, he needs you to output how to obtain a valid bracket sequence. A bracket sequence is valid if it is an empty string, or can be written as $(A)$ or $AB$, where $A$ and $B$ are arbitrary valid bracket sequences.

Input Format

The first line contains an integer $t$, representing the number of bracket sequences. The following lines describe these $t$ sequences.

The first line contains an integer $n$, representing the number of bracket pairs in the sequence.

The second line contains a string $z$ of length $2n$, consisting only of characters ( and ).

The next $n$ lines each contain two integers $a_i, b_i$, where the numbers $1, 2, \dots, 2n$ appear exactly once.

Output Format

Output $t$ lines, each containing a $01$ sequence representing the possible bracket selection scheme. For the $i$-th sequence, if the bracket at index $a_j$ of the $j$-th pair is selected, output $0$; if the bracket at index $b_j$ is selected, output $1$. If there is no valid selection scheme, output $-1$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0 1 0 1

Input Sample #2

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

Output Sample #2

1 1 0 0

Input Sample #3

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

Output Sample #3

-1

Notes/Hints

Sample Explanation 1:

From the original sequence ()))(((), only the bold parts will remain ()))(((), resulting in ()(), which is a valid bracket sequence.

Data Range:

For $9\%$ of the data: $1 \le n \le 10$.

For $9\%$ of the data: $z[a_i] = z[b_i]$.

For $18\%$ of the data: $b_i = a_i + 1$.

For $100\%$ of the data: $1 \le t \le 10^5, \sum n \le 10^5, 1 \le n \le 10^5, 1 \le a_i \le b_i \le 2 \times n$.

This problem has the same scoring as COCI 2021-2022#6, with a maximum score of $110$ points.

见题面 Input 部分

见题面 Output 部分