题目描述

语言学家 Elio 设计了一套由排列生成的奇怪文法。给定一个 $1$ 到 $n$ 的排列，他把每个整数 $1,2,\ldots,n$ 都看作一个非终结符。

对于整数 $k$，它的展开规则如下：在给定排列中找出所有不超过 $k$ 的整数，并按它们在排列中的相对顺序组成一个列表。

例如，当 $n=4$，排列为

时，展开规则为

现在从只包含一个符号 $n$ 的列表开始。每一步中，Elio 会把当前列表中的每个整数都按照对应规则展开，得到一个新的列表。重复这个过程 $s$ 步。

最终列表可能很长。Elio 不想真的把它全部写出来，于是给你 $q$ 个询问。每个询问包含整数 $k$ 和前缀长度 $a$，要求你回答：最终列表的前 $a$ 个元素中，整数 $k$ 出现了多少次。

输入格式

第一行包含三个整数 $n,s,q$，分别表示排列大小、展开步数和询问数量。

接下来 $n$ 行，每行包含一个整数，按顺序给出排列。

接下来 $q$ 行，每行包含两个整数 $k,a$，表示一个询问。

保证 $a$ 不超过最终列表的长度。

输出格式

对每个询问，按输入顺序输出一行一个整数，表示最终列表前 $a$ 个元素中 $k$ 的出现次数。

数据范围

• $2\le n\le 10^5$；
• $1\le s\le 5$；
• $1\le q\le 2\cdot 10^5$；
• $1\le k\le n$；
• $1\le a\le 10^9$；
• 输入的 $n$ 个数构成 $1$ 到 $n$ 的排列。

样例 1

输入

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

输出

3
6
0
1
2
8