給定一個長度為 n 的括號序列，要求支持兩種操作： 1. 將 [Li, Ri] 區(qū)間內(nèi)（序列中的第 Li 個字符到第 Ri 個字符）的括號全部翻轉(zhuǎn)（左括號變成右括號，右括號變成左括號）。 2. 求出以 Li 為左端點(diǎn)時，最長的合法括號序列對應(yīng)的 Ri （即找出最大的Ri 使 [Li, Ri] 是一個合法括號序列）。
輸入
輸入的第一行包含兩個整數(shù) n, m，分別表示括號序列長度和操作次數(shù)。 第二行包含給定的括號序列，括號序列中只包含左括號和右括號。 接下來 m 行，每行描述一個操作。如果該行為 “1 Li Ri”，表示第一種操作，區(qū)間為 [Li, Ri] ；如果該行為 “2 Li” 表示第二種操作，左端點(diǎn)為 Li。
輸出
對于每個第二種操作，輸出一行，表示對應(yīng)的 Ri。如果不存在這樣的 Ri，請輸出 0。
樣例輸入
7 5
((())()
2 3
2 2
1 3 5
2 3
2 1
樣例輸出
4
7
0
0
提示
【評測用例規(guī)模與約定】 對于 20% 的評測用例，n, m ≤ 5000； 對于 40% 的評測用例，n, m ≤ 30000； 對于 60% 的評測用例，n, m ≤ 100000； 對于所有評測用例，1 ≤ n ≤ 106, 1 ≤ m ≤ 2 × 105。