题目描述

丹不仅是 OI 之神、whk 之神，还是游戏之神。

对于一个字符串 $T$，定义一次行走为你选择一个任意长度（不妨设长度为 $m$）的正整数序列 $t_1,t_2,\ldots,t_m$，其中 $\forall i \in [1,m],t_i\in [1,|T|]$，$\forall i \in [2,m], |t_i-t_{i-1}|=1$，$t_1\not=t_m$ 并且 $T_{t_1}T_{t_2}\ldots T_{t_m}$ 是一个回文串，在这次行走后我们认为你经过了 $t_1,t_2,\ldots t_m$ 这些位置各一次。

称一个字符串是“配得上丹”的，当且仅当你可以通过若干次行走使得这个字符串的每个位置都被经过至少一次。

现在给定一个长度为 $n$ 的字符串 $S$，有 $q$ 次询问，第 $i$ 次询问给出两个数 $l_i, r_i$，你需要判断 $S$ 中 $l_i$ 到 $r_i$ 的这个子串是否是“配得上丹”的。

输入格式

从文件 pass.in 中读入数据。

第一行一个正整数 $n$ 表示字符串 $S$ 的长度。

第二行一个长度为 $n$ 的仅包含英文小写字母的字符串描述 $S$。

第三行一个正整数 $q$ 表示询问数量。

接下来 $q$ 行，每行两个正整数 $l_i, r_i$ 表示一次询问。

输出格式

输出到文件 pass.out 中。

方便起见，你只需要输出长度为 $q$ 的 $01$ 串，其中第 $i$ 个位置等于 $1$ 当且仅当第 $i$ 次询问的字符串是“配得上丹”的。

样例

样例 1

7
danaand
3
2 6
4 5
1 3

110

第一次询问的字符串为 anaan，方便起见令 $T=$anaan，那么你可以行走一次 $(1, 2, 3, 4, 5, 4)$，满足起点终点不重合并且得到的字符串 anaana 是一个回文串。

第二次询问的字符串为 aa，方便起见令 $T=$aa，那么你可以行走一次 $(2, 1)$，满足起点终点不重合并且得到的字符串 aa 是一个回文串。

第三次询问的字符串为 dan，不难发现这个字符串“配不上丹”。

样例 2

8
bcdbacab
10
5 6
2 7
1 5
1 5
2 7
4 8
4 6
2 4
1 5
3 3

0100110000

样例 3

见选手目录下的 pass/pass3.in 与 pass/pass3.ans。

该样例满足测试点 $6 \sim 9$ 的性质。

数据范围

对于所有测试点，满足 $1\le n,q\le 10^6$，$1\le l_i\le r_i\le n$。

每个测试点的具体限制见下表：

测试点编号	$n$	$q$	特殊性质
$1\sim 2$	$\le 5$	$\le 10$	无
$3\sim 5$	$\le 50$	$\le 500$
$6\sim 9$	$\le 2000$
$10\sim 13$	$\le 10^5$
$14\sim 15$	$\le 10^6$		$\text{A}$
$16\sim 20$			无

特殊限制 $\text{A}$：保证给定字符串 $S$ 中只包含两种字母 a 和 b。