Задача A. Отрезки с наложением

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дано N отрезков с длинами w1, …, wN. Требуется расположить их на интервале числовой оси [0, L] так, чтобы они покрыли этот интервал без пропусков и не выходили за его границы.

Необходимо использовать все отрезки. Отрезки можно накладывать друг на друга.

Формат входного файла

Первая строка входного файла содержит целые числа N и L.

Вторая строка содержит N целых чисел w1 w2… wN.

Формат выходного файла

Выходной файл должен содержать N целых чисел x1 x2… xN — координаты левых концов отрезков.

Если решения не существует, то выходной файл должен содержать единственное число  − 1. Если существует несколько решений, вывести любое из них.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ L ≤ 10000, 1 ≤ wi ≤ 10000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
2 2
0 1

Разбор

Если сумма всех wi меньше L или максимальное wi больше L, то покрыть отрезок длиной L невозможно.

Иначе координаты левых концов отрезков можно выбрать, например, так:


0.132s 0.013s 15