题目描述

给定一个长度为 $n$ 的括号序列，要求支持两种操作：

1. 将 $[L_i, R_i]$ 区间内（序列中的第 $L_i$ 个字符到第 $R_i$ 个字符）的括号全部翻转（左括号变成右括号，右括号变成左括号）。
2. 求出以 $L_i$ 为左端点时，最长的合法括号序列对应的 $R_i$（即找出最大的 $R_i$ 使 $[L_i, R_i]$ 是一个合法括号序列）。

输入描述

输入的第一行包含两个整数 $n, m$，分别表示括号序列长度和操作次数。

第二行包含给定的括号序列，括号序列中只包含左括号和右括号。

接下来 $m$ 行，每行描述一个操作。如果该行为 “$1\ L_i\ R_i$”，表示第一种操作，区间为 $[L_i, R_i]$；如果该行为 “$2\ L_i$” 表示第二种操作，左端点为 $L_i$。

输出描述

对于每个第二种操作，输出一行，表示对应的 $R_i$。如果不存在这样的 $R_i$，请输出 $0$。

7 5
((())()
2 3
2 2
1 3 5
2 3
2 1

4
7
0
0

评测用例规模与约定

对于 20% 的评测用例，$n, m ≤ 5000$；

对于 40% 的评测用例，$n, m ≤ 30000$；

对于 60% 的评测用例，$n, m ≤ 100000$；

对于所有评测用例，$1 ≤ n ≤ 10^6 , 1 ≤ m ≤ 2 × 10^5$。