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