C. Хорошая задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Juggernaut. - Lost Dream feat.星名はる

Даны четыре целых положительных числа $$$n, l, r, k$$$. Необходимо найти лексикографически наименьший$$$^{\text{∗}}$$$ массив $$$a$$$ длины $$$n$$$, состоящий из целых чисел, такой что:

Если такой массив не существует, выведите $$$-1$$$. В противном случае, поскольку весь массив может быть очень большим, выведите только $$$a_k$$$.

$$$^{\text{∗}}$$$Массив $$$a$$$ лексикографически меньше массива $$$b$$$, если и только если выполняется одно из следующего:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$; или
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в массиве $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Каждый набор входных данных содержит четыре целых положительных числа $$$n,l,r,k$$$ ($$$1 \le k \le n \le 10^{18}$$$, $$$1 \le l \le r \le 10^{18}$$$).

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

Для каждого набора входных данных выведите $$$a_k$$$ или $$$-1$$$, если ни один массив не соответствует условиям.

Пример
Входные данные
9
1 4 4 1
3 1 3 3
4 6 9 2
4 6 9 3
4 6 7 4
2 5 5 1
2 3 6 2
999999999999999999 1000000000000000000 1000000000000000000 999999999999999999
1000000000000000000 1 999999999999999999 1000000000000000000
Выходные данные
4
1
6
8
-1
-1
-1
1000000000000000000
2
Примечание

В первом наборе входных данных массив $$$a = [4]$$$. Можно доказать, что не существует массива, который соответствует вышеуказанным требованиям и имеет меньший лексикографический порядок.

Во втором наборе входных данных массив $$$a= [1,1,1]$$$. Можно доказать, что не существует массива, который соответствует вышеуказанным требованиям и имеет меньший лексикографический порядок.

В третьем и четвертом наборах входных данных массив $$$a = [6,6,8,8]$$$. Можно доказать, что не существует массива, который соответствует вышеуказанным требованиям и имеет меньший лексикографический порядок.

В пятом и шестом наборах входных данных можно доказать, что не существует массива, который соответствует вышеуказанным требованиям.