题号：NC16737
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
给出一个长度为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≤ i≤ 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，输出一行，表示答案
示例1
输入
复制
11
11011100010
5
3 2 3
2 6 8 5
1 2 5 3
4 8
4 100
说明
第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
备注:
保证1 ≤ l ≤ r ≤ 01串在操作前的长度；
01串的长度始终不超过108；
1≤ n,m ≤ 105；
在操作1,2,4中，1 ≤ k ≤ 108。