T3 二进制回文字符串

题目信息

时间限制: 1s

空间限制: 256M

输入文件: manacher.in

输出文件: manacher.out

题目描述

称一个长度为 $2^k$ 的字符串 $s$ 是二进制回文的，当且仅当 $\forall i\in [0, 2^k)$，记 $i$ 写成 $k$ 位二进制数后为 $\overline{a_1 a_2 \ldots a_k}$，对于十进制数 $j=\overline{a_k a_{k-1} \ldots a_1}$，有 $s_i=s_j$。注意 $s$ 的下标从 0 开始，描述 $k$ 位二进制数时前导 0 不可忽略。

给出一个长度为 $n$ 的由小写字母组成的字符串 $t$，请回答以下格式的 $Q$ 个询问：

• 给出两个数 $p, k(0\leq p< n, k\leq 19)$，求 $t$ 的子串 $t_pt_{p+1}\dots t_{p+2^k-1}$ 是否是二进制回文的。注意，处理询问时需要认为子串 $t_pt_{p+1}\dots t_{p+2^k-1}$ 的下标范围是 $[0, 2^k)$，若 $p+2^k > n$，则直接认为该询问的子串不是二进制回文的。

输入格式

第一行两个正整数 $n, Q\left(1 \leq n, Q \leq 5 \times 10^5\right)$，含义如题所示。

第二行一个长度为 $n$ 的字符串 $t$，保证 $t$ 仅由小写字母组成。

接下来 $Q$ 行每行两个正整数 $p, k(0 \leq p<n, k \leq 19)$，表示一个询问。

输出格式

对于每个询问，若对应子串是二进制回文的，输出 1，否则输出 0。

样例

样例输入 1

8 4
axxyxxyb
0 3
1 1
0 2
3 2

样例输出 1

1
1
1
1

数据范围与提示

对于所有数据 $1 \leq n, Q \leq 5 \times 10^5$。