0 and 1 in BIT

题号：NC254994
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

There are many $0$ and $1$ in both bit and BIT.

In BIT, the definition of $0$ and $1$ is also somehow ambiguous. $0$ can sometimes become $1$ and vice versa.

Now, given an event string containing only $A$ and $B$ with length $n$ , you're required to answer $Q$ questions $(l_{real},r_{real},x)$ which ask what will binary string $x$ be after experiencing the events in interval $[l_{real},r_{real}]$ (The leftmost bit is the most significant bit for $x$ ).

Here's the illustration for the event $A$ , $B$ .

$A$ : change $0$ in $x$ to $1$ and change $1$ in $x$ to $0$ simultaneously.

$B$ : execute $x=x+1$ where $x$ is viewed as an integer in binary representation. Specially, if $x$ contains only $1$ , $x$ will become a binary string with all $0$ .

You are required to answer each problem online. For this propose, if we ask $(l,r)$ in the $i-$ th query, it means the actually asked segment is defined as:

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

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

where $\oplus$ is the exclusive OR operation and $ans_{i-1}$ is the answer for the $(i-1)-$ th query (viewed as an integer in binary representation) with $ans_0=0$ .

输入描述:

The first line contains two integers, , the length of event string and the number of queries.

The second line contains the event string  and  contains only  and .

In the following  lines, each line contains a query , and  is a binary string containing only  and .

输出描述:

For each query, output the binary representation of  after the events in interval .

示例1

输入

复制

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

输出

复制

0011
111
0101010110

说明

The actually asked segments in the samples are , respectively.