8984: 0 and 1 in BIT

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 (lreal,rreal,x)(l_{real},r_{real},x)(lreal,rreal,x) which ask what will binary string $x$ be after experiencing the events in interval [lreal,rreal][l_{real},r_{real}][lreal,rreal] (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)(l,r)(l,r) in the $i-$th query, it means the actually asked segment is defined as:

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

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

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

The first line contains two integers, n(3≤n≤2×105),q(1≤q≤2×105)n(3\leq n\leq 2\times 10^5),q(1\leq q\leq 2\times 10^5)n(3≤n≤2×105),q(1≤q≤2×105), the length of event string and the number of queries.
The second line contains the event string S(∣S∣=n)S(|S|=n)S(∣S∣=n) and $S$ contains only $A$ and $B$.
In the following $q$ lines, each line contains a query l,r,x(1≤l≤r≤n,1≤∣x∣≤50)l,r,x(1\leq l\leq r\leq n, 1\leq |x| \leq 50)l,r,x(1≤l≤r≤n,1≤∣x∣≤50), and $x$ is a binary string containing only $0$ and $1$.

For each query, output the binary representation of $x$ after the events in interval [l,r][l,r][l,r].

The actually asked segments in the samples are $(2,9),(1,7),(2,4)$, respectively.