#594 Parentheses Flip

Statement

Statement language

You are given a parenthesis string $S$ of length $2N$ . Flipping the $i$ -th character costs $A_i$ . A flip changes ( to ) and ) to (.

A string $S$ is called a regular bracket sequence if it can be defined by the following rules.

The empty string is a regular bracket sequence.
If $S$ is a regular bracket sequence, then $\texttt{(}S\texttt{)}$ is also a regular bracket sequence.
If $S$ and $T$ are regular bracket sequences, then $ST$ is also a regular bracket sequence.

Only strings that can be obtained by applying the above rules a finite number of times are regular bracket sequences.

Flip some characters of $S$ to make it a correct parenthesis string. Print the minimum possible cost and one resulting string attaining that cost.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $S$ $A_1\ A_2\ \cdots\ A_{2N}$

Output

For each test case, first print the minimum cost on one line.

On the next line, print any correct parenthesis string obtainable with that minimum cost.

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq N \leq 200\,000$ .
$S$ has length $2N$ and consists only of ( and ).
$1 \leq A_i \leq 10^9$ ( $1 \leq i \leq 2N$ ).
The sum of $N$ over all test cases does not exceed $200\,000$ .

Subtasks

#	Score	Constraints
1	6	$N \leq 8$ . The sum of $N$ over all test cases does not exceed $32$ .
2	15	$S$ is already a correct parenthesis string.
3	28	$N \leq 2\,000$ . The sum of $N$ over all test cases does not exceed $2\,000$ .
4	51	No additional constraints.

Samples

Input

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

Output

1
(())
8
()(())

In the first test case, flipping the second character changes the string to $\texttt{(())}$ at a cost of $1$ . It is impossible to obtain a valid parenthesis string at cost $0$ , so the minimum cost is $1$ .

Editorial

View editorial