# [集训队互测 2023] 落日珊瑚

## 题目描述

给一个长度为 $n$、包含方括号和圆括号的括号串，定义一个串 $S$ 合法，当且仅当以下几种情况之一：

1.  $S$ 为空串；
1.  $S= [T]$ 且 $T$ 合法；
1.  $S= (T)$ 且 $T$ 合法；
1.  $S=TU$ 且 $T, U$ 合法。

比如 ```()```，```[()]``` 都是一个合法的括号串，但 ```[()]())``` 不是。

定义一个操作叫选择一个区间 $[l, r]$，并把所有在区间里的字符从方括号变圆括号，从圆括号变方括号。

定义一个括号串的权值 $val(S)$ 为：如果这个括号串能通过操作变成合法，就是最小的操作次数；否则是 $0$。

给出 $q$ 次修改查询，有以下两种可能。

1.  修改，给出一个区间 $[l, r]$ 把所有在区间里的字符从方括号变圆括号，从圆括号变方括号。
2.  查询，给出一个区间 $[l, r]$，求 $\sum_{[l', r'] \in [l, r]} val(s[l', r'])$。

## 输入格式

第一行四个整数 $n, q, T, subtaskid$，分别表示字符串长度，操作次数，强制在线的参数，子任务编号。

接下来一行一个长度为 $n$ 的字符串。

接下来 $q$ 行，每行三个数 $opt, L, R$，表示一次操作。

强制在线，真实的 $l = \min((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$，$r = \max((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$ 其中 $lastans$ 是上一次询问的答案，如果没有上次询问则为 $0$。

**请注意，即使是离线的部分分，也有可能 $L \neq l$，$R \neq r$**。

## 输出格式

若干行，每次询问输出一个答案。

## 样例 #1

### 样例输入 #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
```

### 样例输出 #1

```
1
0
0
1
0
0
```

## 样例 #2

### 样例输入 #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
```

### 样例输出 #2

```
2
0
0
1
2
1
0
4
```

## 提示

对于所有数据，$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$。

| 子任务编号 |  $n, q \le $  | 特殊性质 | 分值 |
| :--------: | :-----------: | :------: | :--: |
|     1      |      $100$      |    E     |  5   |
|     2      |     $6000$      |    E     |  5   |
|     3      |    $10^5$     |    AE    |  5   |
|     4      | $2\cdot 10^5$ |    BE    |  5   |
|     5      | $2\cdot 10^5$ |   CDE    |  5   |
|     6      | $2\cdot 10^5$ |    CE    |  10  |
|     7      | $2\cdot 10^5$ |    DE    |  10  |
|     8      | $2\cdot 10^5$ |    E     |  10  |
|     9      | $2\cdot 10^5$ |    无    |  20  |
|     10     | $5\cdot 10^5$ |    无    |  25  |



A 性质：每个位置有 $\frac{1}{4}$ 的概率为方圆左右括号。

B 性质：保证没有修改。

C 性质：保证修改为单点修改。

D 性质：保证查询区间 $[l, r]$ 满足 $S[l, r]$ 经过若干次操作可以变成合法串，且不存在另一个 $k \in [l, r)$，使得 $S[l, k]$ 可以经过若干次操作变成合法串。

E 性质：保证 $T = 0$，即可以离线。