Given a $01$ string $S$ of length $n$ (a sequence consisting of $0$s and $1$s, with indices from $1$ to $n$).

The following operations are supported:

Operation 1: Given $l, r, k$, repeat the substring from index $l$ to $r$ $k$ times and replace the original segment with the result.

Operation 2: Given $l, r, k$, repeat the substring from index $l$ to $r$ $k$ times with flips and replace the original segment with the result. Specifically, for the $i$-th repetition ($1 \leq i \leq k$), if the binary representation of $i-1$ contains an odd number of $1$s, the segment is reversed; otherwise, it remains unchanged.

Operation 3: Given $l, r$, delete the substring from index $l$ to $r$.

Operation 4: Given $k$, find the position of the $k$-th $1$ in the $01$ string from left to right. If $k$ exceeds the total number of $1$s in the string, output $-1$.

Input

The first line contains an integer $n$.

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

The next line contains an integer $m$.

The next $m$ lines each start with an integer $op$ representing the operation type.

If $op=1$ or $op=2$, the line continues with three integers $l, r, k$.

If $op=3$, the line continues with two integers $l, r$.

If $op=4$, the line continues with one integer $k$.

Output

For each operation 4, output a single line containing the answer.

Examples

Input 1

11
11011100010
5
3 2 3
2 6 8 5
1 2 5 3
4 8
4 100

Output 1

10
-1

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

It is guaranteed that $1 \leq l \leq r \leq$ the current length of the $01$ string.

In operations $1, 2, 4$, $1 \leq k \leq 10^8$.

For $20\%$ of the data, $n, m$ and the length of the $01$ string never exceed $20$.

For $40\%$ of the data, there is only one operation 4, and no operation 2.

For $100\%$ of the data, $1 \leq n, m \leq 10^5$, and the length of the $01$ string never exceeds $10^8$.

Note

Explanation of the example:

Operation 1: 1[10]11100010 -> 111100010, deleted 10.

Operation 2: 11110[001]0 -> 11110[001, 100, 100, 001, 100]0 -> 111100011001000011000, repeated 001 five times, where the 2nd, 3rd, and 5th repetitions were flipped.

Operation 3: 1[1110]0011001000011000 -> 1[1110, 1110, 1110]0011001000011000 -> 11110111011100011001000011000, repeated 1110 three times.

Operation 4: 111101110[1]1100011001000011000, the 8th $1$ is at the 10th position in the $01$ string.

Operation 5: There are not 100 $1$s, so output -1.