| Codeforces Round 394 (Div. 2) |
|---|
| Закончено |
Войдя в систему, Даша принялась решать задачи. Одна из них звучала следующим образом:
По данным двум последовательностям a и b длины n необходимо построить последовательность c длины n, i-й элемент которой вычисляется следующим образом: ci = bi - ai.
Об a и b также известно, что их элементы лежат в интервале от l до r. Более формально, выполняются равенства l ≤ ai ≤ r и l ≤ bi ≤ r. Про последовательность c известно, что все ее элементы различны.
Решение задачи Даша написала быстро, но вот проверить ее работу на стандартном тесте оказалось не так просто. Из-за ошибки в системе тестирования из теста была известна только последовательность a и сжатая последовательность последовательности c.
Дадим определение сжатой последовательности. Сжатой последовательностью последовательности c длины n будем считать такую последовательность p длины n, что pi равно количеству чисел, меньше либо равных чем ci, в последовательности c. К примеру, для последовательности c = [250, 200, 300, 100, 50] сжатой последовательностью является p = [4, 3, 5, 2, 1]. Обратите внимание, что в c все числа различны. Следовательно, сжатая последовательность содержит все числа от 1 до n включительно.
Помогите Даше найти любую последовательность b, для которой посчитанная сжатая последовательность последовательности c верна.
В первой строке находятся три целых числа n, l, r (1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ 109) — длина последовательностей и границы отрезка, в котором лежат элементы a и b.
В следующей строке входных данных находятся n целых чисел a1, a2, ..., an (l ≤ ai ≤ r) — элементы последовательности a.
В следующей строке входных данных находятся n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n) — сжатая последовательность последовательности c.
Если подходящей последовательности b не существует, то в единственной строке выходных данных выведите «-1».
Иначе в единственной строке выходных данных должно содержаться n целых чисел — элементы любой подходящей последовательности b.
5 1 5
1 1 1 1 1
3 1 5 4 2
3 1 5 4 2
4 2 9
3 4 8 9
3 2 1 4
2 2 2 9
6 1 5
1 1 1 1 1 1
2 3 5 4 1 6
-1
Найденная во втором примере последовательность b является подходящей, потому что построенная последовательность c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1, - 2, - 6, 0] (напомним, что ci = bi - ai) имеет сжатую последовательность равную p = [3, 2, 1, 4].
