Kotlin Heroes: Episode 8 |
---|

Finished |

The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 8:

- Kotlin 1.7.20
- Kotlin 1.9.21

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

*special problem

bitmasks

dp

greedy

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Fix the String

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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.

Input

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$$$.

Output

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.

Example

Input

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

Output

2 0 0 4 1 -1

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/24/2024 03:52:20 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|