#2334. 希蒙的二进制游戏

希蒙的二进制游戏

希蒙的二进制游戏

题目背景

临近CSP,希蒙做了很多题目训练,希望取得好成绩,但某一天,他突然发现他的训练计划里面竟然没有二进制数相关的题目,这怎么行,于是他出了一个...

题目描述

给定一个操作的字符串,这个字符串中只包含"A"和"B",含义如下:

我们最初有一个数xx,我们将对其依次按照操作序列执行操作。

对于A操作,我们执行x=x+1x=x+1

对于B操作,我们对xx中的0,10,1反转。例如10111011,操作后变为01000100

我们一共有qq次询问,每次给你操作序列的区间(l,r)(l,r)(包含边界)与源操作数xx,你需要输出xx在进行了(l,r)(l,r)的操作以后的值。

本题强制在线,所以请你仔细阅读下列要求:

$l_{real}=min((ans_{i-1}⊕l)\%n+1,(ans_{i-1}⊕r)\%n+1)$

$r_{real}=max((ans_{i-1}⊕l)\%n+1,(ans_{i-1}⊕r)\%n+1)$

⊕表示异或运算,ansi1ans_{i-1}表示第i1i-1次询问的答案,特别的,ans0=0ans_0=0

输入格式

第一行两个整数n,qn,q,表示操作序列的长度与询问个数。

第二行一个字符串,表示操作的序列。

接下来一共qq行,每行三个数l,r,xl,r,x,其中xx是以二进制形式呈现。

输出格式

你一共需要输出qq行,输出xix_i经过变化后的值,请按二进制形式输出,且不要忽略前导0。

样例 #1

样例输入 #1

10 3
BAABABABBA
1 8 0001
3 5 110
6 10 0101010101

样例输出 #1

0011
111
0101010110

提示

数据范围:

对于30%的数据,我们保证1<=n,q<=1031<=n,q<=10^3

对于100%的数据,我们保证1<=n,q<=2105,1<=x<=501<=n,q<=2\cdot10^5,1<=|x|<=50