Given a bracket sequence of length $n$ containing square brackets and parentheses, a string $S$ is defined as valid if and only if it satisfies one of the following conditions:

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

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

An operation is defined as choosing an interval $[l, r]$ and flipping all characters within that interval: square brackets become parentheses, and parentheses become square brackets.

The weight $val(S)$ of a bracket sequence is defined as: if the bracket sequence can be transformed into a valid sequence through operations, it is the minimum number of operations required; otherwise, it is 0.

You are given $q$ queries of two types: 1. Update: Given an interval $[l, r]$, flip all characters within that interval. 2. Query: Given an interval $[l, r]$, calculate $\sum_{[l', r'] \in [l, r]} val(s[l', r'])$.

Input

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

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

The next $q$ lines each contain three integers $opt, L, R$, representing an operation.

The queries are forced online. The actual indices are:

$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)$

where $lastans$ is the answer to the previous query, or $0$ if there was no previous query.

Note: Even for offline subtasks, it is possible that $L \neq l$ and $R \neq r$.

Output

Output the answer for each query on a new line.

Examples

Input 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 1

1
0
0
1
0
0

Input 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 2

2
0
0
1
2
1
0
4

Note 3

See the provided files.

Constraints

$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$.

Property A: Each position has a $\frac{1}{4}$ probability of being one of the four bracket types.

Property B: No updates are performed.

Property C: Updates are guaranteed to be point updates.

Property D: The query interval $[l, r]$ is guaranteed to be such that $S[l, r]$ can be transformed into a valid string through some operations, and there exists no other $k \in [l, r)$ such that $S[l, k]$ can be transformed into a valid string through some operations.

Property E: $T = 0$ is guaranteed, meaning the problem can be solved offline.