Bracket Sequence Operations

You are given a bracket sequence of length \( n \) consisting of characters '(' and ')'. You need to support two types of operations:

1. Given two indices \( L_i \) and \( R_i \), flip all brackets in the interval \( [L_i, R_i] \) (i.e. change every '(' to ')' and vice versa).
2. Given an index \( L_i \), determine the maximum \( R_i \) (with \( R_i \ge L_i \)) such that the substring \( [L_i, R_i] \) is a valid bracket sequence. A valid bracket sequence is defined in the usual way (every prefix has nonnegative balance and the total balance equals 0). If no such \( R_i \) exists, output -1.

Note: All indices are 1-indexed.

inputFormat

The first line contains two integers \( n \) and \( q \) representing the length of the sequence and the number of operations respectively.

The second line contains a string of length \( n \) consisting of characters '(' and ')'.

The following \( q \) lines each represent an operation. The format of each operation is as follows:

• For a flip operation: 1 L R (flip all brackets from index \( L \) to \( R \)).
• For a query operation: 2 L (query for the maximum \( R \) for the valid bracket sequence starting at \( L \)).

outputFormat

For each query operation (operation type 2), output a single line containing one integer: the maximum \( R \) such that the substring \( [L, R] \) forms a valid bracket sequence, or -1 if no such \( R \) exists.

sample

6 5
(()())
2 1
1 2 3
2 1
1 1 6
2 3

6
6
-1