F. Путешествие по Берляндии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии $$$n$$$ городов, расположенных по кругу и пронумерованных от $$$1$$$ до $$$n$$$ по часовой стрелке.

Мы хотим объехать всю Берляндию, начав в каком-то городе, посетив все остальные города и вернувшись в стартовый город. К сожалению, ехать мы можем только по Берляндской Кольцевой Автодороге, соединяющей все $$$n$$$ городов. Проектировал дорогу очень титулованный и респектабельный министр, поэтому она односторонняя — по ней можно ехать только по часовой стрелке, то есть только из города $$$i$$$ в город $$$(i \bmod n) + 1$$$ (т.е. из $$$1$$$ в $$$2$$$, из $$$2$$$ в $$$3$$$, ..., из $$$n$$$ в $$$1$$$).

Бензобак машины вмещает до $$$k$$$ литров бензина. На пути $$$i$$$-го города в следующий машина расходует $$$a_i$$$ литров бензина.

В каждом городе есть заправка; литр бензина на заправке в $$$i$$$-м городе стоит $$$b_i$$$ бурлей. Заправляться между городами нельзя; если бензин закончился между городами, то такая поездка считается незавершенной.

Для каждого города посчитайте минимальную стоимость путешествия, если оно должно начаться и закончиться в нем.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — количество городов и объем бензобака, соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 2$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, где $$$i$$$-е из них равно минимальной стоимости путешествия, если начать и закончить в $$$i$$$-м городе.

Пример
Входные данные
4
3 5
3 4 4
1 2 2
5 7
1 3 2 5 1
2 1 1 1 2
4 3
1 2 1 3
2 2 2 2
3 2
2 2 2
1 2 1
Выходные данные
17 19 17 
13 12 12 12 14 
14 14 14 14 
8 8 8