J2. Изменение массива (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.

Дан массив из $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$.

Разрешается изменить значения некоторых элементов массива. После изменений все элементы также должны оставаться натуральными числами.

Требуется получить массив, сумма элементов которого равна $$$S$$$, изменив минимально возможное количество элементов исходного массива.

Если это возможно, выведите любой подходящий массив с минимальным количеством изменённых элементов. Если получить сумму $$$S$$$ невозможно, выведите $$$-1$$$.

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

В первой строке записаны два целых числа $$$n$$$ и $$$S$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le S \le 10^9$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Если решения не существует, выведите $$$-1$$$.

Иначе выведите $$$n$$$ натуральных чисел — изменённый массив. Его сумма должна быть равна $$$S$$$, а количество позиций, в которых он отличается от исходного массива, должно быть минимально возможным.

Пример
Входные данные
5 14
3 4 5 2 8
Выходные данные
3 2 5 2 2
Примечание

В примере изначально сумма чисел в массиве равна $$$22 = 3 + 4 + 5 + 2 + 8$$$, изменив второй и пятый элемент добились суммы $$$14 = 3 + 2 + 5 + 2 + 2$$$. Заметим, что изменением одного элемента нельзя было обойтись, ибо числа должны остаться натуральными.