У Игоря была перестановка \(p_1, p_2, \ldots, p_n\). К сожалению, перестановка выглядела достаточно скучно, так что он решил выбрать несколько непересекающихся подотрезков перестановки и развернуть каждый из них. Стоимость разворота одного отрезка \([l, r]\) (то есть элементов на позициях с \(l\) по \(r\) включительно) равна \(r - l\), а общая стоимость одной операции равна сумме стоимостей разворота для соответствующих отрезков. Игорю на Новый Год подарили целое число \(c\), поэтому его интересуют лишь те операции, стоимость которых не превосходит \(c\).
Затем Игорю стало совсем скучно, и он решил выписать на листочек все перестановки, которые он может получить из исходной, проделав ровно одну операцию. Каждую перестановку он выписал ровно один раз, даже если какую-то перестановку можно было получить несколькими способами. Полученный список Игорь отсортировал лексикографически.
Теперь Денис решил задать Игорю несколько вопросов про его список. Каждый вопрос выглядит следующим образом: чему равно \(i\)-е число в \(j\)-й перестановке в списке Игоря? Разумеется, Игорю слишком скучно заниматься ответами на эти вопросы, так что он обратился к вам за помощью.
Выходные данные
Для каждого вопроса в отдельной строке выведите ответ на этот вопрос или \(-1\), если Игорь ошибся и \(j\)-й перестановки не существует на листочке Игоря.
Примечание
В первом примере Игорь выписал на листочек следующие перестановки: \([1, 2, 3]\), \([1, 3, 2]\), \([2, 1, 3]\).
Обратите внимание, что для получения перестановки \([3, 2, 1]\) Игорю пришлось бы развернуть весь массив, а стоимость такой операции равна \(2\), что больше указанного значения \(c=1\). Другие две перестановки не могут быть получены из исходной путем применением операции из условия задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
1
12 4 2
1 2 3 4 5 6 7 8 9 10 11 12
2 20
2 21
|
2
2
|