310284: CF1809F. Traveling in Berland

F. Traveling in Berlandtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $n$ cities in Berland, arranged in a circle and numbered from $1$ to $n$ in clockwise order.

You want to travel all over Berland, starting in some city, visiting all the other cities and returning to the starting city. Unfortunately, you can only drive along the Berland Ring Highway, which connects all $n$ cities. The road was designed by a very titled and respectable minister, so it is one-directional — it can only be traversed clockwise, only from the city $i$ to the city $(i \bmod n) + 1$ (i.e. from $1$ to $2$, from $2$ in $3$, ..., from $n$ to $1$).

The fuel tank of your car holds up to $k$ liters of fuel. To drive from the $i$-th city to the next one, $a_i$ liters of fuel are needed (and are consumed in the process).

Every city has a fuel station; a liter of fuel in the $i$-th city costs $b_i$ burles. Refueling between cities is not allowed; if fuel has run out between cities, then your journey is considered incomplete.

For each city, calculate the minimum cost of the journey if you start and finish it in that city.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($3 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the number of cities and the volume of fuel tank, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 2$).

The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print $n$ integers, where the $i$-th of them is equal to the minimum cost of the journey if you start and finish in the $i$-th city.

ExampleInput

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

Output

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

题目大意：
贝尔兰有 $ 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 $ 个城市出发并结束旅程的最少旅行费用。

示例输入输出已在题目中给出。题目大意： 贝尔兰有 $ 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 $ 个城市出发并结束旅程的最少旅行费用。 示例输入输出已在题目中给出。