A. Ladder
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are standing in front of a huge ladder consisting of $$$n$$$ steps (let's assume you are initially on the step $$$0$$$). You want to climb as high as possible, and to do that, you have $$$x$$$ energy points and a choice of two actions:

  1. Climb up one step higher. To climb to the $$$i$$$-th step from the $$$i-1$$$-th step, you must spend $$$a_i$$$ energy points. If your current energy reserve is less than $$$a_i$$$, you will not be able to climb to the $$$i$$$-th step;
  2. Teleport to one step higher without spending energy but using one teleport charge.

Unfortunately, you do not know how many teleport charges you have left. Therefore, for each number of teleport charges from $$$0$$$ to $$$n-1$$$, determine the maximum step you can reach.

Input

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

The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 3 \cdot 10^5; 1 \le x \le 10^{15}$$$) — the number of steps and the initial amount of energy, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of energy points needed to climb to the $$$i$$$-th step (while being on the $$$i-1$$$-th step).

Output

For each test case, print the answer in the following format.

In a single line, print $$$n$$$ numbers $$$s_0, s_1, \dots, s_{n-1}$$$, where $$$s_i$$$ is the maximum step you can reach while spending no more than $$$i$$$ teleport charges.

Example
Input
3
4 5
10 11 15 100
4 1337
1 10 100 1000
5 1
1000 1001 1002 1003 1004
Output
0 1 2 3 
4 4 4 4 
0 1 2 3 4