← 返回题目列表

Codeforces · 1571/E

E. 修复字符串

中文机器翻译题面 查看原题

正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如:

- 括号序列“()()”和“(())”是正则表达式(结果表达式为:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。

给定两个字符串 $$$s$$$ 和 $$$a$$$,字符串 $$$s$$$ 的长度为 $$$n$$$,字符串 $$$a$$$ 的长度为 $$$n - 3$$$。字符串 $$$s$$$ 是一个括号序列(即该字符串的每个元素都是左括号字符或右括号字符)。字符串 $$$a$$$ 是一个二进制字符串(即该字符串的每个元素不是 1 就是 0)。

字符串 $$$a$$$ 对字符串 $$$s$$$ 施加了一些约束:对于每个 $$$i$$$ ,使得 $$$a_i$$$ 为 1,字符串 $$$s_i s_{i+1} s_{i+2} s_{i+3}$$$ 应该是常规括号序列。 $$$a$$$ 等于 0 的字符不会施加任何限制。

最初,字符串 $$$s$$$ 可能满足也可能不满足这些约束。您可以多次执行以下操作:将 $$$s$$$ 的某些字符替换为其反义字符(即,您可以将左括号替换为右括号,反之亦然)。

确定是否可以更改 $$$s$$$ 中的某些字符,使其满足所有约束,如果可以,计算要更改的最小字符数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由三行组成。第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 2 \cdot 10^5$$$)。第二行包含字符串 $$$s$$$,恰好由 $$$n$$$ 个字符组成; $$$s$$$ 的每个字符都是“(”或“)”。第三行包含字符串 $$$a$$$,恰好由 $$$n - 3$$$ 个字符组成; $$$a$$$ 的每个字符不是“1”就是“0”。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数:$$$s$$$ 中需要更改的最小字符数,如果不可能,则打印 $$$-1$$$。

示例

输入 #1

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

输出 #1

2
0
0
4
1
-1