题目描述

圆给了你一个长度为 $n$ 的字符串 $S$，$S$ 仅由 ( 和 ) 构成。

她会对其做 $m$ 次操作，操作有两种类型：

1. 1 l r，她会翻转 $l$ 到 $r$ 的括号，即 ( 变 )，) 变 (。
2. 2 l r，她想知道区间 $\left[ l,r\right]$ 中最长合法括号子序列的长度除以 $2$ 的答案。

圆认为以下的括号序列是合法的：

1. 空序列是一个合法序列。

2. 如果 A 是一个合法序列，则 (A) 也是一个合法序列。

3. 如果 A 和 B 都是合法序列，则 AB 也是一个合法序列。

圆认为，序列 $a$ 的子序列是满足 $1\le i_1<i_2<···<i_k \le n$ 的序列 $[a_{i_1},a_{i_2},...a_{i_k}]$。

由于操作太多了，她算不过来，请你帮帮她吧。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串 $S$，保证仅由 ( 和 ) 构成 。

第三行一行一个整数 $m$。

接下来 $m$ 行，每行三个数 $op$，$l$，$r$，对应上面的两种操作。

输出格式

对于每一个 $op=2$ 的操作，输出一行一个整数，表示答案。

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

1
0
1
2

提示

【样例解释】

• 第一次截取的字符串是 ()，答案为 $1$。
• 翻转后字符串变为 ))(())。
• 第二次截取的字符串是 )(，答案为 $0$。
• 第三次截取的字符串是 ())，答案为 $1$。
• 第四次截取的字符串是 (())，答案为 $2$。

【数据范围】

• 对于 $10\%$ 的数据，$1 \leq n,m \leq 500$；
• 对于 $20\%$ 的数据，$1 \leq n,m \leq 5000$；
• 对于 $40\%$ 的数据，$1 \leq n,m \leq 2\times 10^5$；
• 另有 $10\%$ 的数据，满足 $op=2$ 且数据随机生成；
• 另有 $15\%$ 的数据，满足 $op=2$ 但不保证数据随机生成；

对于所有数据，保证 $1\le n \le 5\times 10^5$，$1\le m \le 5 \times 10^5$，$1 \le l \le r \le n$，$op \in \{1,2\}$。数据有梯度。