Рассмотрим перестановку чисел от $1$ до $n$. Будем считать каждое число от $1$ до $n$ нетерминалом в контекстно-свободной грамматике (КС-грамматике). Каждое число $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$, где на каждом шаге мы применяем эти правила для создания нового списка целых чисел. В примере выше на первом шаге:

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

На втором шаге:

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

На третьем шаге:

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

Дана перестановка, количество шагов и список запросов, спрашивающих количество вхождений конкретного целого числа в префикс списка, созданного в результате этого процесса. Ответьте на все запросы.

Входные данные

Первая строка входных данных содержит три целых числа: $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