Перестановка — это последовательность длины \(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\), подходящую под условие выше. Если существует несколько подходящих перестановок, выведите любую из них.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите:
- \(n\) целых чисел — перестановку длины \(n\), обладающую свойством из условия, если такая перестановка существует;
- -1, иначе.
Если существует несколько подходящих перестановок, выведите любую из них.