Problem Description

The world-famous physicist Juraj has recently discovered a new fundamental particle—the parenthesision. A parenthesision can be in one of two states: open ( or close ). Using Juraj’s homemade particle accelerator, he created $t$ superposed sequences, each consisting of $n$ parenthesisions. The $n$ parenthesisions in each of these $t$ sequences are superpositions of two different positions and (not necessarily different) states. If the sequence is observed, the wave function of the parenthesisions collapses, and then the position and state of each parenthesision become fixed. Juraj wants to know whether these parenthesisions can collapse into a valid bracket sequence.

Dr. Juraj M. knows that the quantum physics of these revolutionary and fully science-based particles is beyond the knowledge scope of COCI contestants, so he provides a formal statement:

You are given $t$ bracket sequences of length $2n$ consisting of left and right brackets. Each bracket belongs to exactly one pair. The two brackets in a pair can be different, or they can both be left brackets or both be right brackets. Juraj wants to know whether it is possible to choose one bracket from each pair so that the resulting bracket sequence is a valid bracket sequence. Also, if it is possible, you need to output how to obtain such a valid bracket sequence. A bracket sequence is valid if it is an empty string, or it can be written as $(A)$ or $AB$, where $A$ and $B$ are any valid bracket sequences.

Input Format

The first line contains an integer $t$, the number of bracket sequences. The next $t$ sequences are described as follows.

The first line contains an integer $n$, the number of bracket pairs in this 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$. Each number $1, 2, \dots, 2n$ appears in them exactly once.

Output Format

Output $t$ lines. On the $i$-th line, output a $01$ sequence representing a possible bracket selection plan. If in the $i$-th sequence, for the $j$-th pair, the bracket with index $a_j$ is chosen, output $0$; if $b_j$ is chosen, output $1$. If there is no valid selection plan, output $-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

Hint

Sample Explanation 1:

From the original sequence ()))(((), only the bold parts remain: ()))(((), that is ()(), which is a valid bracket sequence.

Constraints

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

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

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

For $100\%$ of the testdata: $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$.

The score of this problem is the same as in COCI 2021-2022#6, with a full score of $110$ points.

Translated by ChatGPT 5