Rozważmy permutację liczb od $1$ do $n$. Niech każda liczba od $1$ do $n$ będzie symbolem nieterminalnym w gramatyce bezkontekstowej (CFG). Każda liczba $k$ rozwija się w listę liczb od $1$ do $k$ w kolejności zgodnej z permutacją. Na przykład, jeśli $n = 4$, a permutacja to $1\ 4\ 3\ 2$:

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

Rozważmy proces rozpoczynający się od $n$, w którym w każdym kroku stosujemy powyższe reguły, aby utworzyć nową listę liczb. W powyższym przykładzie, w pierwszym kroku:

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

W drugim kroku:

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

W trzecim kroku:

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

Mając daną permutację, liczbę kroków oraz listę zapytań o liczbę wystąpień konkretnej liczby w prefiksie listy utworzonej przez ten proces, odpowiedz na wszystkie zapytania.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n$ ($2 \le n \le 10^5$), $s$ ($1 \le s \le 5$) oraz $q$ ($1 \le q \le 2 \cdot 10^5$), gdzie $n$ to rozmiar permutacji, $s$ to liczba kroków procesu, a $q$ to liczba zapytań.

Każda z kolejnych $n$ linii zawiera pojedynczą liczbę całkowitą $p$ ($1 \le p \le n$). Jest to permutacja w podanej kolejności. Wszystkie wartości $p$ są różne.

Każda z kolejnych $q$ linii zawiera dwie liczby całkowite $k$ ($1 \le k \le n$) oraz $a$ ($1 \le a \le 10^9$, $a$ nie przekroczy długości końcowej listy). Jest to zapytanie o liczbę wystąpień liczby $k$ w pierwszych $a$ elementach listy utworzonej przez proces.

Wyjście

Wypisz $q$ linii, każda z pojedynczą liczbą całkowitą, będącą odpowiedzią na zapytanie w kolejności ich występowania na wejściu.

Przykład

Wejście 1

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

Wyjście 1

3
6
0
1
2
8