Problem Description

Given a string of length $n$ containing square brackets and parentheses, a string $S$ is considered valid if and only if one of the following conditions holds:

1. $S$ is an empty string;
2. $S = [T]$ and $T$ is valid;
3. $S = (T)$ and $T$ is valid;
4. $S = TU$ and both $T$ and $U$ are valid.

For example, () and [()] are valid bracket strings, but [()]()) is not.

Define an operation that selects an interval $[l, r]$ and changes all characters within this interval from square brackets to parentheses and vice versa.

Define the value $val(S)$ of a bracket string as follows: if the string can be made valid through operations, it is the minimum number of operations required; otherwise, it is $0$.

Given $q$ modification queries, there are two possible types:

1. Modify: Provide an interval $[l, r]$ to change all characters within this interval from square brackets to parentheses and vice versa.
2. Query: Provide an interval $[l, r]$ to find $\sum_{[l', r'] \in [l, r]} val(s[l', r'])$.

Input Format

The first line contains four integers $n, q, T, subtaskid$, representing the length of the string, the number of operations, the parameter for forced online, and the subtask number.

The next line is a string of length $n$.

The following $q$ lines, each containing three numbers $opt, L, R$, represent an operation.

The input is forced online. The actual $l = \min((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$, and $r = \max((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$, where $lastans$ is the answer to the previous query, or $0$ if there was no previous query.

Note that even for offline partial scores, it is possible that $L \neq l$ and $R \neq r$.

Output Format

Several lines, each containing the answer to a query.

Sample Input and Output

Input Sample #1

10 10 0 0
[)]]((()][
2 10 6
1 6 6
1 3 6
2 5 7
2 3 3
2 10 4
1 7 1
2 4 4
2 4 2
1 5 5

Output Sample #1

1
0
0
1
0
0

Input Sample #2

20 20 0 0
[)])[)[](()((]]([[)[
2 9 3
2 8 10
1 4 15
1 5 9
1 16 10
1 18 20
1 1 8
2 8 9
1 2 16
1 10 13
1 16 9
1 8 1
2 20 7
2 14 11
1 3 16
1 15 18
1 6 4
2 10 7
2 2 4
2 13 2

Output Sample #2

2
0
0
1
2
1
0
4

Notes/Hints

For all data, $1 \le n, q \le 5 \cdot 10^5$, $0 \le T \le 10^9$, $1 \le l, r \le n$, $1 \le opt \le 2$.

A Property: Each position has a $\frac{1}{4}$ probability of being a square or round bracket.

B Property: No modifications are guaranteed.

C Property: Modifications are guaranteed to be point modifications.

D Property: Guaranteed that the query interval $[l, r]$ satisfies $S[l, r]$ can be made valid through several operations, and there is no other $k \in [l, r)$ such that $S[l, k]$ can be made valid through several operations.

E Property: Guaranteed $T = 0$, i.e., can be offline.

见题面 Input 部分

见题面 Output 部分