题目描述

给定一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$。

我们称另一个长度为 $n$ 的序列是排列 $p$ 的一个 循环移位，当且仅当我们可以通过执行若干次（可能 $0$ 次）如下操作是排列 $p$ 变成这个序列：

将排列 $p$ 当前的首元素取出并放到排列 $p$ 的末尾。

比如：排列 $(2, 1, 3)$ 一共有 $3$ 个不同的循环移位，它们是 $(2, 1, 3)$，$(1, 3, 2)$，$(3, 2, 1)$。

现在还给了你一个长度为 $m$ 的序列 $a_1, a_2, \ldots, a_m$ 以及 $q$ 次询问。

第 $i$ 次询问给你两个整数 $l_i$ 和 $r_i$，你需要判断出序列 $a$ 从第 $l$ 个元素到第 $r$ 个元素（包括第 $l$ 个和第 $r$ 个元素）对应的这段序列中能否取出一个子序列，该子序列是排列 $p$ 的一个循环移位。

即：你需要判断是否能够找到 $n$ 个下标 $i_1, i_2, \ldots, i_n$ 满足 $l_i \le i_1 \lt i_2 \lt \ldots \lt i_n \le r_i$ 且序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_n}$ 是排列 $p$ 的一个循环移位。

输入格式

第一行，三个整数 $n, m, q(1 \le n,m,q \le 2 \cdot 10^5)$，以空格分隔。

第二行，$n$ 个整数 $p_1, p_2, \ldots, p_n$，两两之间以一个空格分隔，表示一个排列。

第三行，$m$ 个整数 $a_1, a_2, \ldots, a_m(1 \le a_i \le n)$，两两之间以一个空格分隔。

接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le m$），以一个空格分隔，表示一次询问。

输出格式

输出一个仅由字符 1 和 0 构成的字符串。

对于第 $i$ 次询问，如果区间 $[l_i, r_i]$ 存在至少一个子序列是排列 $p$ 的一个循环移位，则第 $i$ 个字符为 1，否则第 $i$ 个字符为 0。

样例

3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5

110

2 4 3
2 1
1 1 2 2
1 2
2 3
3 4

010

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n,m,q \le 20$
• 对于 $50\%$ 的数据，$n,m,q \le 2000$
• 对于 $100\%$ 的数据，$1 \le n,m,q \le 2 \cdot 10^5$