Operations on a Binary String

You are given a binary string \(S\) of length \(n\) (containing only characters 0 and 1 with indices from \(1\) to \(n\)). You need to process \(q\) operations on this string. There are four types of operations:

Operation 1: Given three integers \(l, r, k\), take the substring \(S[l...r]\) and replace this segment with its repetition exactly \(k\) times. In other words, update \[ S = S[1\ldots l-1] \; + \; (S[l\ldots r])^k \; + \; S[r+1\ldots n]. \]

Operation 2: Given three integers \(l, r, k\), take the substring \(S[l...r]\) and replace it with \(k\) copies. For the \(i\)-th copy (where \(1 \le i \le k\)), you should check the binary representation of \(i-1\). If the number of ones in the binary representation of \(i-1\) is odd, then use the reverse of \(S[l...r]\) for that copy; otherwise, use \(S[l...r]\) as it is. Formally, if we denote the segment by \(T=S[l\ldots r]\), then the new segment is \[ T_1 \; \Vert \; T_2 \; \Vert \; \cdots \; \Vert \; T_k, \quad \text{where } T_i = \begin{cases} T, & \text{if } \mathrm{popcount}(i-1) \text{ is even};\\ T^{R}, & \text{if } \mathrm{popcount}(i-1) \text{ is odd}. \end{cases} \] and \(T^R\) denotes the reverse of string \(T\). Then update \[ S = S[1\ldots l-1] \; + \; (T_1\Vert T_2 \Vert \cdots \Vert T_k) \; + \; S[r+1\ldots n]. \]

Operation 3: Given two integers \(l, r\), delete the substring \(S[l...r]\) from \(S\). That is, update \[ S = S[1\ldots l-1] \; + \; S[r+1\ldots n]. \]

Operation 4: Given an integer \(k\), find the \(k\)-th occurrence of the character '1' in the current string (from left to right). If \(k\) is greater than the total number of '1's in \(S\), output \(-1\).

Input Format:

• The first line contains the initial binary string \(S\).
• The second line contains an integer \(q\) representing the number of operations.
• The following \(q\) lines each describe an operation in one of the following formats:
  • For Operation 1 and Operation 2: op l r k (where op is either 1 or 2).
  • For Operation 3: 3 l r.
  • For Operation 4: 4 k.

Output Format:

For each Operation 4, output the answer on a new line.

inputFormat

The input begins with a line containing the binary string \(S\). The next line contains an integer \(q\), the number of operations. This is followed by \(q\) lines, each describing one operation as detailed above.

outputFormat

For every operation of type 4, print a single line containing the 1-indexed position of the \(k\)-th '1' in the current string \(S\). If there are fewer than \(k\) ones, print \(-1\).

sample

10101
7
4 3
1 2 3 2
4 4
2 1 3 3
4 7
3 2 5
4 5

5
7
11
7