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