E. Странная перестановка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Игоря была перестановка $$$p_1, p_2, \ldots, p_n$$$. К сожалению, перестановка выглядела достаточно скучно, так что он решил выбрать несколько непересекающихся подотрезков перестановки и развернуть каждый из них. Стоимость разворота одного отрезка $$$[l, r]$$$ (то есть элементов на позициях с $$$l$$$ по $$$r$$$ включительно) равна $$$r - l$$$, а общая стоимость одной операции равна сумме стоимостей разворота для соответствующих отрезков. Игорю на Новый Год подарили целое число $$$c$$$, поэтому его интересуют лишь те операции, стоимость которых не превосходит $$$c$$$.

Затем Игорю стало совсем скучно, и он решил выписать на листочек все перестановки, которые он может получить из исходной, проделав ровно одну операцию. Каждую перестановку он выписал ровно один раз, даже если какую-то перестановку можно было получить несколькими способами. Полученный список Игорь отсортировал лексикографически.

Теперь Денис решил задать Игорю несколько вопросов про его список. Каждый вопрос выглядит следующим образом: чему равно $$$i$$$-е число в $$$j$$$-й перестановке в списке Игоря? Разумеется, Игорю слишком скучно заниматься ответами на эти вопросы, так что он обратился к вам за помощью.

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

В первой строке дано целое число $$$t$$$ ($$$1 \leq t \leq 30$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$c$$$, $$$q$$$ ($$$1 \leq n \leq 3 \cdot 10^4$$$, $$$1 \leq c \leq 4$$$, $$$1 \leq q \leq 3 \cdot 10^5$$$) — размер перестановки, максимальная стоимость операции и число вопросов.

В следующей строке содержатся $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$, $$$p_i \neq p_j$$$ если $$$i \neq j$$$) — элементы исходной перестановки.

В каждой из следующих $$$q$$$ содержатся описания вопросов, каждое описание состоит из двух целых чисел $$$i$$$ и $$$j$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq j \leq 10^{18}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$, и что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого вопроса в отдельной строке выведите ответ на этот вопрос или $$$-1$$$, если Игорь ошибся и $$$j$$$-й перестановки не существует на листочке Игоря.

Примеры
Входные данные
2
3 1 9
1 2 3
1 1
2 1
3 1
1 2
2 2
3 2
1 3
2 3
3 3
6 4 4
6 5 4 3 1 2
1 1
3 14
1 59
2 6
Выходные данные
1
2
3
1
3
2
2
1
3
1
4
-1
5
Входные данные
1
12 4 2
1 2 3 4 5 6 7 8 9 10 11 12
2 20
2 21
Выходные данные
2
2
Примечание

В первом примере Игорь выписал на листочек следующие перестановки: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$.

Обратите внимание, что для получения перестановки $$$[3, 2, 1]$$$ Игорю пришлось бы развернуть весь массив, а стоимость такой операции равна $$$2$$$, что больше указанного значения $$$c=1$$$. Другие две перестановки не могут быть получены из исходной путем применением операции из условия задачи.