Problem Description

You are given a bracket string of length $n$ consisting of square brackets and parentheses. A string $S$ is defined to be valid if and only if it satisfies one of the following:

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 as follows: choose an interval $[l, r]$, and for every character in the interval, change square brackets to parentheses, and change parentheses to square brackets.

Define the value $val(S)$ of a bracket string $S$ as: if this string can be turned into a valid string using operations, then $val(S)$ is the minimum number of operations needed; otherwise, it is $0$.

You are given $q$ update/query operations of two types:

1. Update: given an interval $[l, r]$, change every character in the interval from square brackets to parentheses, and from parentheses to square brackets.
2. Query: given an interval $[l, r]$, compute $\sum_{[l', r'] \in [l, r]} val(s[l', r'])$.

Input Format

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

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

Then follow $q$ lines, each containing three numbers $opt, L, R$, representing one operation.

Online is enforced. 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; if there was no previous query, then it is $0$.

Please note that even for offline subtasks, it is still possible that $L \neq l$ and $R \neq r$.

Output Format

Output several lines. For each query, output one answer.

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

1
0
0
1
0
0

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

2
0
0
1
2
1
0
4

Hint

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

Property A: At each position, each of the four bracket types has probability $\frac{1}{4}$.

Property B: It is guaranteed that there are no updates.

Property C: It is guaranteed that each update is a single-point update.

Property D: It is guaranteed that for the query interval $[l, r]$, $S[l, r]$ can be turned into a valid string after some operations, and there does not exist another $k \in [l, r)$ such that $S[l, k]$ can be turned into a valid string after some operations.

Property E: It is guaranteed that $T = 0$, i.e., the problem can be solved offline.

Input Format

Output Format

Hint

Translated by ChatGPT 5