Problem Description

Given a parentheses sequence of length $n$, you need to support two types of operations:

1. Flip all parentheses in the interval $\left[L_{i}, R_{i}\right]$ (from the $L_{i}$-th character to the $R_{i}$-th character in the sequence). That is, left parentheses become right parentheses, and right parentheses become left parentheses.

2. Given $L_{i}$ as the left endpoint, find the $R_{i}$ of the longest valid parentheses sequence (i.e., find the maximum $R_{i}$ such that $\left[L_{i}, R_{i}\right]$ is a valid parentheses sequence).

Input Format

The first line contains two integers $n, m$, representing the length of the parentheses sequence and the number of operations.

The second line contains the given parentheses sequence, which only consists of left parentheses and right parentheses.

The next $m$ lines each describe an operation. If the line is 1 L R, it means the first type of operation with interval $\left[L, R\right]$; if the line is 2 L, it means the second type of operation with left endpoint $L$.

Output Format

For each operation of the second type, output one line with the corresponding $R_{i}$. If no such $R_{i}$ exists, output $0$.

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

4
7
0
0

Hint

For $20\%$ of the testdata, $n, m \leq 5000$.

For $40\%$ of the testdata, $n, m \leq 30000$.

For $60\%$ of the testdata, $n, m \leq 100000$.

For all testdata, $1 \leq n \leq 10^{6}, 1 \leq m \leq 2 \times 10^{5}$.

Lanqiao Cup 2021 National Contest Group A Problem H (Group B Problem I).

Translated by ChatGPT 5