В Берляндии $$$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$$$-м городе.
43 53 4 41 2 25 71 3 2 5 12 1 1 1 24 31 2 1 32 2 2 23 22 2 21 2 1
17 19 17 13 12 12 12 14 14 14 14 14 8 8 8
