题目描述

题目译自 Romanian Master of Informatics 2020 Day1 T2 「Brperm」

注意：在以下描述中，$\overline{b_{1} \ldots b_{k}}$ 表示一个以二进制表示的整数，其中 $b_{1}$ 是最高有效位，$b_{k}$ 是最低有效位。

太空女巫 Roxanne 在骑着她的扫帚穿越银河系时，发现了一个奇怪的星球——Br-PERM 星球。在这个星球上，每个人都跳一种奇怪的舞蹈：这场舞蹈中，你需要排成一列，然后重新调整自己的位置。假设有 $2^{k}$ 个人在跳舞，那么位置 $\overline{b_{1} \ldots b_{k}}$ 的人会移动到位置 $\overline{b_{k} \ldots b_{1}}$（编号从 $0$ 开始）。

Roxanne 还注意到，Br-PERM 星球上的每个人都穿着 $26$ 种颜色之一的衣服，这些颜色由拉丁字母表示。

Br-PERM 星球的人们对舞者在跳舞前后衣服颜色序列相同的情况赋予了特殊的意义，他们称这种序列为完美的。例如，当 $k=2$ 时，我们有一排四个舞者 $0,1,2,3$，跳舞后他们的顺序变为：$0,2,1,3$。因此，衣服颜色序列 abba 是完美的，但 abca 不是。

Br-PERM 星球的人们请 Roxanne 帮助他们解决一个难题（太空女巫似乎总是要帮助别人解决问题）。他们展示了一长排 $n$ 个舞者，并问她几个问题：「从第 $i$ 个舞者开始，长度为 $2^{k}$ 的序列是否是完美的？」

实现细节

你必须实现两个函数。第一个函数如下：

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

这个函数将在交互开始时被调用一次，并通过参数 $s$ 向你提供舞者的衣服颜色字符串。

你必须实现的第二个函数是：

int query(int i, int k);

这个函数将被调用 $Q$ 次，只有当从第 $i$ 个舞者（编号从 $0$ 开始）开始，长度为 $2^{k}$ 的连续子序列是完美的时，才返回 $1$。否则返回 $0$。保证子序列不会超过 $s$ 的末尾。

样例

输入

init(8, "axxyxxyb")

输出

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

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 5 \cdot 10^5$
• $1 \leq Q \leq 5 \cdot 10^5$

详细子任务附加限制及分值如下表所示。