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