← 返回题目列表

Codeforces · 1809/F

F. 在贝尔兰旅行

中文机器翻译题面 查看原题

Berland 有 $$$n$$$ 个城市,排列成圆圈,按顺时针顺序从 $$$1$$$ 到 $$$n$$$ 编号。

您想要环游 Berland,从某个城市出发,参观所有其他城市,最后返回出发城市。不幸的是,您只能沿着连接所有 $$$n$$$ 城市的 Berland Ring 高速公路行驶。这条路是由一位非常有头衔和受人尊敬的部长设计的,所以它是单向的——只能顺时针穿过,只能从城市 $$$i$$$ 到城市 $$$(i \bmod n) + 1$$$ (即从 $$$1$$$ 到 $$$2$$$,从 $$$2$$$ in $$$3$$$,...,从 $$$n$$$ 到$$$1$$$)。

您汽车的油箱最多可容纳 $$$k$$$ 升燃油。要从第 $$$i$$$ 个城市行驶到下一个城市,需要 $$$a_i$$$ 升燃料(并在此过程中消耗)。

每个城市都有加油站;在第 $$$i$$$ 个城市,一升燃料的价格为 $$$b_i$$$ burles。不允许城市间加油;如果城市之间的燃料耗尽,那么您的旅程将被视为不完整。

对于每个城市,计算在该城市开始和结束旅程的最低费用。

输入

第一行包含一个整数 $$$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$$$ 个城市开始和结束的旅程的最低成本。

示例

输入 #1

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

输出 #1

17 19 17 
13 12 12 12 14 
14 14 14 14 
8 8 8