Премия за четверть: распределение без перегруза

В школе учитель информатики раздаёт m бонусных баллов за четверть между n учениками.

Про каждого ученика i заранее известно:

• он должен получить не меньше l_i баллов (иначе обидится),
• и не больше u_i баллов (иначе «слишком много привилегий»).

Учитель хочет раздать ровно m баллов так, чтобы максимум среди выданных баллов был как можно меньше. Если оптимальных распределений несколько, учитель выбирает то, где последовательность (x_1, x_2, ..., x_n) лексикографически минимальна.

Лексикографически минимальна — значит при сравнении двух распределений смотрим слева направо: где впервые различаются, там меньше то, у которого меньше число.

Формат ввода

Первая строка: два целых числа n и m. Вторая строка: n целых чисел l_1 ... l_n. Третья строка: n целых чисел u_1 ... u_n.

Формат вывода

Выведите n целых чисел x_1 ... x_n — выбранное распределение.

Ограничения

• 1 ≤ n ≤ 200000
• 0 ≤ l_i ≤ u_i ≤ 10^18
• 0 ≤ m ≤ 10^18
• Гарантируется, что существует хотя бы одно распределение: sum(l_i) ≤ m ≤ sum(u_i).
• Значения могут выходить за 32-битный тип (как на олимпиадах), используйте 64-битную арифметику.

Пример

Ввод:

5 17
2 1 3 0 2
5 6 10 4 7

Вывод:

2 3 4 4 4