Brperm

Note: in the following statement, $\overline{b_1 \dots b_k}$ represents an integer written out in binary notation, where $b_1$ is the most significant bit, and $b_k$ is the least significant bit.

Roxanne the space witch, while riding her broomstick throughout the galaxy, came across a planet in which everybody danced a strange dance: planet BR-PERM. In this dance, the participants stand in a line, and then reorder themselves. Suppose $2^k$ people are dancing. Then, the person at position $\overline{b_1 \dots b_k}$ goes to position $\overline{b_k \dots b_1}$ (indexed from $0$).

Roxanne noticed also that every person on BR-PERM wears one of $26$ colors of clothing. These colors are represented by the letters of the Latin alphabet.

The BR-PERM-ians place special significance on rows of dancers where the sequence of colors of clothing that people are wearing before and after the dance are the same. They call such sequences nice. For instance, when $k = 2$, we have a row of four dancers $0$, $1$, $2$, $3$, that after the dance become ordered like so: $0$, $2$, $1$, $3$. So, the sequence of clothing colors abba is nice, but abca is not.

Task

The BR-PERM-ians have asked Roxanne to help them with a difficult matter (space witches always seem to have to help people with their problems). They show her a long row of $n$ dancers, and ask her several questions: "is the sequence of length $2^k$ starting at dancer $i$ nice?".

Interaction protocol

The contestant must implement two functions. The first of them is the following:

void init (int n, const char s[]); 

This function will be called exactly once, at the beginning of the interaction, and supplies the contestant with the string of clothing colors of the dancers, through parameter $s$.

The second function that the contestant must implement is:

int query (int i, int k);

This function will be called exactly $Q$ times and must return $1$ if and only if the contiguous subsequence of $s$ starting at the $i^{\text{th}}$ dancer (indexed from $0$), and of length $2^k$, is nice. It must return $0$ otherwise.

Constraints and clarifications

• $1 \leq N \leq 500 \ 000$
• $1 \leq Q \leq 500 \ 000$

Example

input

init(8, "axxyxxyb")

output

query(0, 3) = true
query(1, 1) = true
query(1, 2) = false
query(3, 2) = true