Full Enough (Hard Version) - Weekly Challenge 1: Approximation | Repovive

W1D1B. Full Enough (Hard Version)

2 pts1s256 MB

You are given $n$ stones. The weight of stone $i$ is $w_i$ .

You have a bag with capacity $W$ . You may choose any subset of stones whose total weight is at most $W$ .

It is guaranteed that there exists a non-empty subset of stones whose total weight is exactly $W$ .

You do not need to find such an exact subset. You only need to choose a subset whose total weight is at least $90\%$ of $W$ and at most $W$ .

Constraints

$1 \le t \le 5$
$1 \le n \le 750$
The sum of $n$ over all test cases is at most $750$
$1 \le W \le 10^{12}$
$1 \le w_i \le W$
There exists a non-empty subset with total weight exactly $W$

Input

The input is given in the following format:

t

\left. \begin{array}{l} n \quad W \\ w_1 \quad w_2 \quad \cdots \quad w_n \end{array} \right\} \times t

Output

For each test case, first output an integer $k$ , the number of chosen stones.

Then output $k$ distinct integers $i_1,i_2,\ldots,i_k$ , the indices of the chosen stones.

The total weight of the chosen stones must be at most $W$ and at least $90\%$ of $W$ .

The output format is:

\left. \begin{array}{l} k \\ i_1 \quad i_2 \quad \cdots \quad i_k \end{array} \right\} \times t

If $k=0$ , the second line may be empty.

Samples

Input

1
8 100
45 45 60 40 30 20 15 5

Explanation

The chosen stones have total weight $45+45=90$ .

This does not fill the bag exactly, but it is still valid because $90$ is exactly $90\%$ of $100$ and does not exceed the capacity.

Output

2
1 2

You are given $n$ stones. The weight of stone $i$ is $w_i$ .

You have a bag with capacity $W$ . You may choose any subset of stones whose total weight is at most $W$ .

It is guaranteed that there exists a non-empty subset of stones whose total weight is exactly $W$ .

You do not need to find such an exact subset. You only need to choose a subset whose total weight is at least $90\%$ of $W$ and at most $W$ .

$1 \le t \le 5$
$1 \le n \le 750$
The sum of $n$ over all test cases is at most $750$
$1 \le W \le 10^{12}$
$1 \le w_i \le W$
There exists a non-empty subset with total weight exactly $W$

The input is given in the following format:

t

\left. \begin{array}{l} n \quad W \\ w_1 \quad w_2 \quad \cdots \quad w_n \end{array} \right\} \times t

For each test case, first output an integer $k$ , the number of chosen stones.

Then output $k$ distinct integers $i_1,i_2,\ldots,i_k$ , the indices of the chosen stones.

The total weight of the chosen stones must be at most $W$ and at least $90\%$ of $W$ .

The output format is:

\left. \begin{array}{l} k \\ i_1 \quad i_2 \quad \cdots \quad i_k \end{array} \right\} \times t

If $k=0$ , the second line may be empty.

The chosen stones have total weight $45+45=90$ .

This does not fill the bag exactly, but it is still valid because $90$ is exactly $90\%$ of $100$ and does not exceed the capacity.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

W1D1B. Full Enough (Hard Version)

Constraints

Input

Output

Samples

W1D1B. Full Enough (Hard Version)

Constraints

Input

Output

Samples