308761: CF1571E. Fix the String

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

• bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
• bracket sequences ")(", "(" and ")" are not.

You are given two strings $s$ and $a$, the string $s$ has length $n$, the string $a$ has length $n - 3$. The string $s$ is a bracket sequence (i. e. each element of this string is either an opening bracket character or a closing bracket character). The string $a$ is a binary string (i. e. each element of this string is either 1 or 0).

The string $a$ imposes some constraints on the string $s$: for every $i$ such that $a_i$ is 1, the string $s_i s_{i+1} s_{i+2} s_{i+3}$ should be a regular bracket sequence. Characters of $a$ equal to 0 don't impose any constraints.

Initially, the string $s$ may or may not meet these constraints. You can perform the following operation any number of times: replace some character of $s$ with its inverse (i. e. you can replace an opening bracket with a closing bracket, or vice versa).

Determine if it is possible to change some characters in $s$ so that it meets all of the constraints, and if it is possible, calculate the minimum number of characters to be changed.

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines. The first line contains one integer $n$ ($4 \le n \le 2 \cdot 10^5$). The second line contains the string $s$, consisting of exactly $n$ characters; each character of $s$ is either '(' or ')'. The third line contains the string $a$, consisting of exactly $n - 3$ characters; each character of $a$ is either '1' or '0'.

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, print one integer: the minimum number of characters that need to be changed in $s$, or $-1$ if it is impossible.

6
4
))((
1
4
))((
0
4
()()
0
6
))(()(
101
6
))(()(
001
5
(((((
11

2
0
0
4
1
-1