题目描述

给出一个长度为 $n$ 的 $01$ 串 $S$（一个由 $0$ 和 $1$ 组成的序列，下标为 $1$ 到 $n$ 的整数）。

支持以下几种操作：

操作1：给出 $l,r,k$，将 $01$ 串下标为 $l$ 到 $r$ 的一段重复 $k$ 次并放回原位；

操作2：给出 $l,r,k$，将 $01$ 串下标为 $l$ 到 $r$ 的一段带翻转地重复 $k$ 次（具体地说，第 $i$（$1\leq i\leq k$）次重复时，若 $i-1$ 的二进制表示中有奇数个 $1$，则这次重复时要左右反转，否则不变），最后放回原位；

操作3：给出 $l,r$，将 $01$ 串下标为 $l$ 到 $r$ 的一段删除；

操作4：给出 $k$，求 $01$ 串中从左到右第 $k$ 个 $1$ 的位置，若 $k$ 超过 $01$ 串中 $1$ 的个数，则输出 $-1$。

输入格式

第一行一个整数 $n$。

接下来一行，一个长度为 $n$ 的 $01$ 串。

接下来一行，一个整数 $m$。

接下来 $m$ 行，每行第一个整数 $op$ 表示操作类型。

若 $op=1$ 或 $op=2$，这一行接下来有三个整数 $l,r,k$。

若 $op=3$，这一行接下来有两个整数 $l,r$。

若 $op=4$，这一行接下来有一个整数 $k$。

输出格式

对每个操作4，输出一行，表示答案。

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

10
-1

提示

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

保证$1\leq l\leq r\leq$ $01$串在操作前的长度；

在操作 $1,2,4$ 中，$1\leq k\leq 10^8$。

对于 $20\%$ 的数据，$n,m$ 以及 $01$ 串的长度始终不超过 $20$；

对于 $40\%$ 的数据，只有一次操作4，且没有操作2。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$01$ 串的长度始终不超过 $10^8$；

样例解释：

第1次操作：1[10]11100010->111100010，删除了10、

第2次操作：11110[001]0->11110[001,100,100,001,100]0->111100011001000011000，将001重复了5次，其中第2,3,5次是翻转的、

第3次操作：1[1110]0011001000011000->1[1110,1110,1110]0011001000011000->11110111011100011001000011000，将1110重复了3次、

第4次操作：111101110[1]1100011001000011000，第8个1在01串中的第10个位置、

第5次操作：不存在100个1，输出-1、