给定一个长度为 n 的括号序列，要求支持两种操作： 1. 将 [Li, Ri] 区间内（序列中的第 Li 个字符到第 Ri 个字符）的括号全部翻转（左括号变成右括号，右括号变成左括号）。 2. 求出以 Li 为左端点时，最长的合法括号序列对应的 Ri （即找出最大的Ri 使 [Li, Ri] 是一个合法括号序列）。
输入格式
输入的第一行包含两个整数 n, m，分别表示括号序列长度和操作次数。 第二行包含给定的括号序列，括号序列中只包含左括号和右括号。 接下来 m 行，每行描述一个操作。如果该行为 “1 Li Ri”，表示第一种操作，区间为 [Li, Ri] ；如果该行为 “2 Li” 表示第二种操作，左端点为 Li。
输出格式
对于每个第二种操作，输出一行，表示对应的 Ri。如果不存在这样的 Ri，请输出 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 ≤ 106, 1 ≤ m ≤ 2 × 105。