Considérons une permutation des entiers de $1$ à $n$. Considérons maintenant chaque nombre de $1$ à $n$ comme un non-terminal dans une grammaire hors-contexte (CFG). Chaque nombre $k$ se développe en une liste des entiers de $1$ à $k$ dans l'ordre de la permutation. Par exemple, si $n = 4$ et que la permutation est $1\ 4\ 3\ 2$ :

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

Considérons maintenant un processus commençant par $n$, et à chaque étape, en appliquant ces règles pour créer une nouvelle liste d'entiers. Dans l'exemple ci-dessus, à la première étape :

$4$ $\downarrow$ $1\ 4\ 3\ 2$

À la deuxième étape :

$1\ 4\ 3\ 2$ $\downarrow \downarrow \downarrow \downarrow$ $1\ (1\ 4\ 3\ 2)\ (1\ 3\ 2)\ (1\ 2)$

À la troisième étape :

$1\ 1\ 4\ 3\ 2\ 1\ 3\ 2\ 1\ 2$ $\downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow$ $1\ 1\ (1\ 4\ 3\ 2)\ (1\ 3\ 2)\ (1\ 2)\ 1\ (1\ 3\ 2)\ (1\ 2)\ 1\ (1\ 2)$

Étant donné une permutation, un nombre d'étapes et une liste de requêtes demandant le nombre d'occurrences d'un entier particulier dans un préfixe de la liste créée par le processus, répondez à toutes les requêtes.

Entrée

La première ligne de l'entrée contient trois entiers, $n$ ($2 \le n \le 10^5$), $s$ ($1 \le s \le 5$) et $q$ ($1 \le q \le 2 \cdot 10^5$), où $n$ est la taille de la permutation, $s$ est le nombre d'étapes à appliquer au processus, et $q$ est le nombre de requêtes.

Chacune des $n$ lignes suivantes contient un entier unique $p$ ($1 \le p \le n$). Il s'agit de la permutation, dans l'ordre. Toutes les valeurs de $p$ seront distinctes.

Chacune des $q$ lignes suivantes contient deux entiers $k$ ($1 \le k \le n$) et $a$ ($1 \le a \le 10^9$, $a$ ne dépassera pas la longueur de la liste finale). Il s'agit d'une requête pour le nombre d'occurrences de l'entier $k$ dans les $a$ premiers éléments de la liste créée par le processus.

Sortie

Affichez $q$ lignes, chacune contenant un seul entier, qui sont les réponses aux requêtes dans l'ordre où elles apparaissent dans l'entrée.

Exemples

Entrée 1

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

Sortie 1

3
6
0
1
2
8