D. Boots n' Jetpacks
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a mountain range consisting of $$$n$$$ mountains, where the $$$i$$$th mountain has height $$$h_i$$$. To traverse the mountain range, you will buy one pair of sturdy boots and any number of jetpacks. Buying boots with sturdiness $$$s$$$ costs $$$a\cdot s$$$ dollars, while buying $$$k$$$ jetpacks costs $$$b \cdot k$$$ dollars. The boots can be reused and allow you to jump over any mountain $$$i$$$ with height $$$h_i \leq s$$$. Each jetpack can only be used once and allows you to jump over any two adjacent mountains.

Find the minimum cost required to jump over the first $$$i$$$ mountains for each $$$i \in \{1, 2, \ldots, n\}$$$. As long as you clear the first $$$i$$$ mountains, it is ok if using a jetpack also happens to take you past the $$$i+1$$$th mountain.

Input

Each test contains multiple test cases. The first line of input contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of input test cases.

The first line of each test case contains $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

The next line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq 10^9$$$) – the cost per unit sturdiness of boots and the cost of a jetpack, respectively.

The next line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_{n}$$$ ($$$1 \leq h_i \leq 10^9$$$) — the heights of the mountains in the mountain range.

It is further guaranteed that the sum of $$$n$$$ over all test cases is at most $$$2\cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers, the $$$i$$$th of which is the minimum required cost to jump over the first $$$i$$$ mountains of that test case.

Example
Input
1
5
2 7
3 2 7 6 4
Output
6 6 13 13 14
Note

For indices $$$i \in \{1, 2, 3, 4\}$$$, it is optimal to buy boots with sturdiness $$$3$$$, which costs $$$6$$$ dollars. For $$$i \in \{1, 2\}$$$, you don't need to buy any jetpacks, and for $$$i \in \{3, 4\}$$$, you need to buy a single jetpack. For $$$i = 5$$$, it is optimal to buy boots with sturdiness $$$7$$$, and no jetpacks.