F. Two Thousand Years Later
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After Najjar travelled from Aleppo to take part in HCPC, it was cancelled. But he decided to stay in Homs, hoping the HCPC will happen. He waited for hours, days, weeks, months and years, but the HCPC didn't happen. Since a regular clock could not measure such a long wait, his teammate Mohannad gave him a magic clock.

Mohannad's magic clock has $$$n$$$ hands, numbered from $$$1$$$ to $$$n$$$. At time $$$0$$$, every hand starts a new cycle.

Hand $$$1$$$ is the fastest hand and needs exactly $$$x$$$ seconds to complete one full cycle.

For each $$$i$$$ from $$$2$$$ to $$$n$$$, one full cycle of hand $$$i$$$ takes as much time as $$$a_i$$$ full cycles of hand $$$i-1$$$.

The rumors say the HCPC will be held after $$$y$$$ seconds. For each hand, determine the number of full cycles it completes during those $$$y$$$ seconds. A cycle completed exactly at time $$$y$$$ is counted.

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 three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le x,y \le 10^{18}$$$) — the number of hands, the duration of one cycle of hand $$$1$$$, and the observed amount of time, respectively.

The second line of the test case contains $$$n-1$$$ integers $$$a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$, where $$$c_i$$$ is the number of full cycles completed by hand $$$i$$$ during the first $$$y$$$ seconds.

Example
Input
5
2 3 10
2
3 2 25
5 10
5 1 100
2 5 2 5
4 10 9
1 1 1
4 6 360
3 4 5
Output
3 1
12 2 0
100 50 10 5 1
0 0 0 0
60 20 5 1
Note

In the second test case, the first hand needs $$$2$$$ seconds to complete a cycle. For the second hand, the first one needs to complete $$$5$$$ cycles so the second completes one cycle. And the second hand completes $$$10$$$ cycles so the third completes one cycle.

In the fourth test case, even the fastest hand cannot complete a cycle within the first $$$9$$$ seconds.