题目背景

译自 8th Romanian Master of Informatics, RMI 2020 D1T2。$\texttt{2s,0.25G}$。

「我，也会有蜕变成蝶的一天吗？」

附件提供了 Sample grader。

提交时，不需要引入 brperm.h。

题目描述

这是一道（函数式）交互题。

定义一个长度为 $2^k$ 的序列 $[a_0,a_1,\cdots,a_{2^k-1}]$ 蝶变之后的结果为 $[a_{\operatorname{rev}(0)},a_{\operatorname{rev}(1)},\cdots,a_{\operatorname{rev}(2^k-1)}]$，其中 $\operatorname{rev}(i)$ 表示将 $i$ 的二进制表示下最低 $k$ 位翻转（reverse）后得到的结果。更为具体地说，令 $i=\overline{b_kb_{k-1}\cdots b_1}$，则 $\operatorname{rev}(i)=\overline{b_1b_{2}\cdots b_k}$。

定义一个长度为 $2^k$ 的序列是美的，当且仅当蝶变后的序列与原序列相同。

给定一个长度为 $N$ 的字符串 $s$，字符集为小写英文字母。$Q$ 次询问给定 $i,k$，问 $s[i:i+2^k-1]$ 是否是美的。

实现细节

你不需要，也不应该实现 main 函数。

你需要实现以下的函数：

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

交互库会调用 init 函数恰好一次。参数的含义：

• N：字符串长度。
• s：字符串。

接下来调用 $Q$ 次 query 函数。这里，$0\le i\lt N$。

注意：不保证 $\textcolor{red}{i+2^k\le N}$。如果 $i+2^k\gt N$，返回 $0$ 即可。

返回 1，代表所查询的子串是美的；否则代表它不是美的。

输入格式

这里提供的是 Sample grader 的输入格式。

第一行，一个字符串 $s$。

接下来若干行，每行两个正整数 $i,k$ 描述一次询问。输入直到 EOF。

输出格式

这里提供的是 Sample grader 的输出格式。

对于每个询问，输出一行一个整数 $\texttt{0}/\texttt{1}$，表示答案。

axxyxxyb
0 3
1 1
0 2
3 2

1
1
1
1

提示

对于 $100\%$ 的数据，保证 $1\le N,Q\le 5\times 10^5$。

• 特殊性质 A：$s$ 中只有字母 $\texttt{a},\texttt{b}$，且每个字母是以某个固定比例独立随机从字符集中选取的。

注意：不保证 $\textcolor{red}{i+2^k\le N}$。如果 $i+2^k\gt N$，返回 $0$ 即可。