你有一个背包,容量为$$$W$$$。还有 $$$n$$$ 项,第 $$$i$$$ 项的重量为 $$$w_i$$$。
您希望将其中一些物品放入背包中,使其总重量 $$$C$$$ 至少为其大小的一半,但(显然)不超过它。形式上,$$$C$$$ 应满足:$$$\lceil \frac{W}{2}\rceil \le C \le W$$$。
输出您将放入背包的物品列表或确定不可能满足条件。
如果有多个可能的满足条件的项目列表,则可以输出任何一个。请注意,您不必最大化背包中物品的重量总和。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,如果没有解决方案,则打印单个整数 $$$-1$$$。
如果存在由 $$$m$$$ 项组成的解决方案,则在输出的第一行中打印 $$$m$$$ 并在第二行中打印 $$$m$$$ 整数 $$$j_1$$$, $$$j_2$$$, ..., $$$j_m$$$ ($$$1 \le j_i \le n$$$,所有 $$$j_i$$$ 都是不同的)输出的 - 您想要装入背包的物品的索引。
如果有多个可能的满足条件的项目列表,则可以输出任何一个。请注意,您不必最大化背包中物品的重量总和。
示例
输入 #1
3 1 3 3 6 2 19 8 19 69 9 4 7 12 1 1 1 17 1 1 1
输出 #1
1 1 -1 6 1 2 3 5 6 7
注意
在第一个测试用例中,您可以取出重量为 $$$3$$$ 的物品并恰到好处地装满背包。
在第二个测试用例中,所有物品都大于背包的容量。因此,答案是$$$-1$$$。
在第三个测试用例中,您将背包正好装满了一半。