该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

希蒙的二进制游戏

题目背景

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

题目描述

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

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

对于A操作，我们执行$x=x+1$。

对于B操作，我们对$x$中的$0,1$反转。例如$1011$，操作后变为$0100$。

我们一共有$q$次询问，每次给你操作序列的区间$(l,r)$（包含边界）与源操作数$x$，你需要输出$x$在进行了$(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)$

⊕表示异或运算，$ans_{i-1}$表示第$i-1$次询问的答案，特别的，$ans_0=0$。

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

0011
111
0101010110

提示

数据范围：

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

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