Butterfly Transformation

This is an interactive function problem. A sequence [a₀, a₁, …, a_2^k-1] is defined such that its butterfly transformation produces a new sequence [a_rev(0), a_rev(1), …, a_rev(2^k-1)], where \(\operatorname{rev}(i)\) means reversing the lowest \(k\) bits of \(i\) in its binary representation. More precisely, if \(i = \overline{b_kb_{k-1}\cdots b_1}\), then \(\operatorname{rev}(i)=\overline{b_1b_2\cdots b_k}\).

A sequence is defined to be beautiful if and only if its butterfly transformation is identical to the original sequence.

You are given a string s of length \(N\) consisting of lowercase English letters. You will receive \(Q\) queries. In each query, you are given two non-negative integers \(i\) and \(k\). For each query, you need to determine whether the substring s[i : i+2^k-1] is beautiful.

Note: If \(i+2^k > N\), you should return 0.

Function Interfaces:

void init(int N, const char s[]);
int query(int i, int k);

The judge will call init exactly once and then invoke query \(Q\) times. Return 1 if the queried substring is beautiful; otherwise, return 0.

inputFormat

The input is provided via function calls. The function init is first called with two parameters:

• N: an integer representing the length of the string.
• s: a string of length N consisting of lowercase English letters.

Afterwards, query is called \(Q\) times. Each query receives two integers i and k.

Note: If i + 2^k > N, the query should return 0 immediately.

outputFormat

The function query should return an integer: 1 if the specified substring is beautiful, and 0 otherwise.

sample

8
abbaabba
3
0 3
1 2
2 2

0
0
1