Considera una permutación de los enteros del 1 al $n$. Ahora, considera que cada número del 1 al $n$ es un no terminal en una Gramática Libre de Contexto (CFG, por sus siglas en inglés). Cada número $k$ expande una lista de los enteros del 1 al $k$ en el orden de la permutación. Por ejemplo, si $n = 4$ y la permutación es 1 4 3 2:

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

Ahora, considera un proceso que comienza con $n$ y, en cada paso, aplica estas reglas para crear una nueva lista de enteros. En el ejemplo anterior, en el primer paso:

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

En el segundo paso:

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

En el tercer paso:

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

Dada una permutación, un número de pasos y una lista de consultas que piden el número de apariciones de un entero particular en un prefijo de la lista creada por el proceso, responde a todas las consultas.

Entrada

La primera línea de entrada contiene tres enteros, $n$ ($2 \le n \le 10^5$), $s$ ($1 \le s \le 5$) y $q$ ($1 \le q \le 2 \cdot 10^5$), donde $n$ es el tamaño de la permutación, $s$ es el número de pasos para aplicar el proceso y $q$ es el número de consultas.

Cada una de las siguientes $n$ líneas contiene un solo entero $p$ ($1 \le p \le n$). Esta es la permutación, en orden. Todos los valores de $p$ serán distintos.

Cada una de las siguientes $q$ líneas contiene dos enteros $k$ ($1 \le k \le n$) y $a$ ($1 \le a \le 10^9$, $a$ no excederá la longitud de la lista final). Esta es una consulta sobre el número de apariciones del entero $k$ en los primeros $a$ elementos de la lista creada por el proceso.

Salida

Imprime $q$ líneas, cada una con un solo entero, que son las respuestas a las consultas en el orden en que aparecen en la entrada.

Ejemplos

Entrada 1

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

Salida 1

3
6
0
1
2
8