Problem Description

Given a $01$ string $S$ of length $n$ (a sequence consisting of $0$ and $1$, indexed by integers from $1$ to $n$).

The following operations are supported:

Operation 1: given $l, r, k$, repeat the substring of the $01$ string from index $l$ to $r$ for $k$ times and put it back in place.

Operation 2: given $l, r, k$, repeat the substring of the $01$ string from index $l$ to $r$ for $k$ times with reversal (specifically, for the $i$-th repetition ($1 \leq i \leq k$), if the binary representation of $i - 1$ contains an odd number of $1$, then this repetition should be reversed left to right; otherwise it remains unchanged), and finally put it back in place.

Operation 3: given $l, r$, delete the substring of the $01$ string 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 number of $1$ in the $01$ string, output $-1$.

Input Format

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$ indicating the operation type.

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

If $op = 3$, the line then contains two integers $l, r$.

If $op = 4$, the line then contains one integer $k$.

Output Format

For each operation 4, output one line representing the answer.

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

10
-1

Hint

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

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

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

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

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

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

Sample explanation:

The 1st operation: 1[10]11100010->111100010, deleted 10.

The 2nd operation: 11110[001]0->11110[001,100,100,001,100]0->111100011001000011000, repeated 001 for 5 times, where the 2nd, 3rd, and 5th times are reversed.

The 3rd operation: 1[1110]0011001000011000->1[1110,1110,1110]0011001000011000->11110111011100011001000011000, repeated 1110 for 3 times.

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

The 5th operation: there is no 100th $1$, output -1.

Translated by ChatGPT 5