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

Перестановка — это последовательность длины $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, в которой все числа встречаются ровно по одному разу. Например, $$$[1]$$$, $$$[3, 5, 2, 1, 4]$$$, $$$[1, 3, 2]$$$ — перестановки, а $$$[2, 3, 2]$$$, $$$[4, 3, 1]$$$, $$$[0]$$$ — нет.

Поликарпу дали четыре целых числа $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n)$$$ и $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$) и попросили найти перестановку $$$p$$$ чисел от $$$1$$$ до $$$n$$$, обладающую следующим свойством:

  • $$$s = p_l + p_{l+1} + \ldots + p_r$$$.

Например, для $$$n=5$$$, $$$l=3$$$, $$$r=5$$$ и $$$s=8$$$ подходят следующие перестановки (перечислены не все варианты):

  • $$$p = [3, 4, 5, 2, 1]$$$;
  • $$$p = [5, 2, 4, 3, 1]$$$;
  • $$$p = [5, 2, 1, 3, 4]$$$.
Но, например, не существует ни одной перестановки, подходящей под условие выше для $$$n=4$$$, $$$l=1$$$, $$$r=1$$$ и $$$s=5$$$.

Помогите Поликарпу для заданных $$$n$$$, $$$l$$$, $$$r$$$ и $$$s$$$ найти перестановку чисел от $$$1$$$ до $$$n$$$, подходящую под условие выше. Если существует несколько подходящих перестановок, выведите любую из них.

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

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

Каждый набор входных характеризуется четырьмя целыми числами $$$n$$$ ($$$1 \le n \le 500$$$), $$$l$$$ ($$$1 \le l \le n$$$), $$$r$$$ ($$$l \le r \le n$$$), $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.

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

Для каждого набора входных данных в отдельной строке выведите:

  • $$$n$$$ целых чисел — перестановку длины $$$n$$$, обладающую свойством из условия, если такая перестановка существует;
  • -1, иначе.

Если существует несколько подходящих перестановок, выведите любую из них.

Пример
Входные данные
5
5 2 3 5
5 3 4 1
3 1 2 4
2 2 2 2
2 1 1 3
Выходные данные
1 2 3 4 5 
-1
1 3 2 
1 2 
-1