考虑一个 $1$ 到 $n$ 的排列。现在，将 $1$ 到 $n$ 中的每个数字视为上下文无关文法（CFG）中的一个非终结符。每个数字 $k$ 都会根据排列的顺序展开为一个 $1$ 到 $k$ 的整数列表。例如，当 $n = 4$ 且排列为 $1\ 4\ 3\ 2$ 时：

$1 \implies 1$ $2 \implies 1\ 2$ $3 \implies 1\ 3\ 2$ $4 \implies 1\ 4\ 3\ 2$

现在，考虑一个从 $n$ 开始的过程，在每一步中，应用这些规则来创建一个新的整数列表。在上面的例子中，第一步：

第二步：

第三步：

给定一个排列、步数以及一系列询问，要求计算在过程生成的列表的前缀中，特定整数出现的次数，请回答所有询问。

输入格式

输入的第一行包含三个整数 $n$ ($2 \le n \le 10^5$)，$s$ ($1 \le s \le 5$) 和 $q$ ($1 \le q \le 2 \cdot 10^5$)，其中 $n$ 是排列的大小，$s$ 是应用该过程的步数，$q$ 是询问的数量。

接下来的 $n$ 行，每行包含一个整数 $p$ ($1 \le p \le n$)。这是按顺序给出的排列。所有 $p$ 的值各不相同。

接下来的 $q$ 行，每行包含两个整数 $k$ ($1 \le k \le n$) 和 $a$ ($1 \le a \le 10^9$，$a$ 不会超过最终列表的长度)。这是一个关于整数 $k$ 在过程生成的列表的前 $a$ 个元素中出现次数的询问。

输出格式

输出 $q$ 行，每行一个整数，按输入顺序给出每个询问的答案。

样例

输入 1

4 3 6
1
4
3
2
1 6
2 20
4 1
3 5
2 9
1 16

输出 1

3
6
0
1
2
8