注：在下文中，$b_1 \dots b_k$ 表示一个用二进制表示的整数，其中 $b_1$ 是最高位，$b_k$ 是最低位。

太空女巫 Roxanne 在骑着扫帚穿越银河系时，偶然发现了一个星球，那里的人们跳着一种奇怪的舞蹈：Br-perm 星球。在这种舞蹈中，参与者排成一列，然后重新排列自己。假设有 $2^k$ 个人在跳舞，那么位置在 $b_1 \dots b_k$ 的人会移动到位置 $b_k \dots b_1$（从 0 开始索引）。

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

Br-perm 星球的人们对舞者队列有一种特殊的重视，如果舞者在跳舞前后所穿衣服颜色的序列相同，他们称这样的序列为“优美的”（nice）。例如，当 $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$ 的 s 的连续子序列是优美的时，必须返回 1。否则返回 0。 保证子序列不会超出 s 的末尾。

数据范围

• $1 \le N \le 500\,000$
• $1 \le Q \le 500\,000$

子任务

子任务 1（13 分）

• $1 \le N \le 1\,000$
• $1 \le Q \le 1\,000$

子任务 2（37 分）

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$

子任务 3（17 分）

• s 仅包含字符 'a' 和 'b'。
• 对于每个测试用例，颜色是根据某个固定概率独立随机选择的。

子任务 4（33 分）

• 无附加限制。

样例

输入 1

init(8, "axxyxxyb")
query(0, 3) = true
query(1, 1) = true
query(0, 2) = false
query(3, 2) = true

输出 1

1
1
0
1