CF1446A.Knapsack

You have a knapsack with the capacity of $W$. There are also $n$ items, the $i$-th one has weight $w_i$.

You want to put some of these items into the knapsack in such a way that their total weight $C$ is at least half of its size, but (obviously) does not exceed it. Formally, $C$ should satisfy: $\lceil \frac{W}{2}\rceil \le C \le W$.

Output the list of items you will put into the knapsack or determine that fulfilling the conditions is impossible.

If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights of items in the knapsack.

你有一个容量为 $W$ 的背包。此外还有 $n$ 个物品，其中第 $i$ 个物品的重量为 $w_i$。

你需要从中选择若干物品放入背包，使得它们的总重量 $C$ 至少为背包容量的一半（向上取整），但又不超过背包容量。形式化地，$C$ 应满足：$\lceil \frac{W}{2}\rceil \le C \le W$。

请输出将要放入背包的物品列表；若无法满足条件，则输出说明该情况不可能。

若存在多种满足条件的物品列表，输出任意一种即可。注意：你不必最大化背包中物品的总重量。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains integers $n$ and $W$ ($1 \le n \le 200\,000$, $1\le W \le 10^{18}$).

The second line of each test case contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$) — weights of the items.

The sum of $n$ over all test cases does not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $W$（$1 \le n \le 200\,000$，$1\le W \le 10^{18}$）。

每个测试用例的第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^9$）—— 各物品的重量。

所有测试用例的 $n$ 值之和不超过 $200\,000$。

For each test case, if there is no solution, print a single integer $-1$.

If there exists a solution consisting of $m$ items, print $m$ in the first line of the output and $m$ integers $j_1$, $j_2$, ..., $j_m$ ($1 \le j_i \le n$, all $j_i$ are distinct) in the second line of the output — indices of the items you would like to pack into the knapsack.

If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights items in the knapsack.

对于每个测试用例，若无解，则输出单个整数 $-1$。

若存在一个由 $m$ 个物品组成的解，则在输出的第一行打印 $m$，在第二行打印 $m$ 个整数 $j_1$, $j_2$, ..., $j_m$（其中 $1 \le j_i \le n$，且所有 $j_i$ 互不相同）——即你希望装入背包的物品的索引。

若存在多个满足条件的物品列表，你可以输出任意一个。注意：你无需最大化背包中物品的总重量。

In the first test case, you can take the item of weight $3$ and fill the knapsack just right.

In the second test case, all the items are larger than the knapsack's capacity. Therefore, the answer is $-1$.

In the third test case, you fill the knapsack exactly in half.

在第一个测试用例中，你可以选择重量为 $3$ 的物品，恰好将背包装满。

在第二个测试用例中，所有物品的重量均大于背包的容量，因此答案为 $-1$。

在第三个测试用例中，你恰好将背包装满一半。