Eulampius 创建了一个具有以下规则的游戏:
- 游戏中有两个玩家:一个人和一台电脑;
- 游戏持续时间不超过 $$$n$$$ 轮。最初,两名玩家都有 $$$0$$$ 点。在第 $$$j$$$ 轮中,人类获得 $$$a_j$$$ 分,计算机获得 $$$b_j$$$ 分。积分同时获得;
- 当其中一名玩家获得 $$$k$$$ 或更多分数时,游戏结束。该玩家输掉了比赛。如果两个玩家同时获得 $$$k$$$ 或更多分数,则双方都输;
- 如果在 $$$n$$$ 轮之后双方玩家的分数均低于 $$$k$$$ ,则游戏以平局结束;
- 每轮结束后,人类可以按下“重置”按钮。如果在按下按钮之前人类有 $$$x$$$ 点,计算机有 $$$y$$$ 点(当然,$$$x < k$$$ 和 $$$y < k$$$),那么按下按钮后人类将有 $$$x' = max(0, \, x - y)$$$ 点,而计算机将有 $$$y' = max(0, \, y - x)$$$ 点。 E. g。按“重置”按钮会将状态 $$$(x=3, \, y=5)$$$ 转换为状态 $$$(x'=0, \, y'=2)$$$,并将状态 $$$(x=8, \, y=2)$$$ 转换为状态 $$$(x'=6, \, y'=0)$$$。
Eulampius 请他的朋友 Polycarpus 测试游戏。 Polycarpus 很快透露,人类和计算机在每一轮 $$$n$$$ 中获得的分数都是在游戏前生成并存储在文件中的。换句话说,按下“重置”按钮不会影响值$$$a_j$$$和$$$b_j$$$,因此序列$$$a$$$和$$$b$$$是固定的并且是预先已知的。
Polycarpus 想要为游戏制定一个计划。他希望尽可能少地按下“重置”按钮来赢得比赛。您的任务是确定最少的推动次数或确定 Polycarpus 无法获胜。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 测试用例的数量。然后是测试用例。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) - 游戏中可能的最大轮数和玩家输掉的分数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_j < k)$$$,其中 $$$a_j$$$ 是人类在第 $$$j$$$ 轮中获得的分数。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_j < k$$$),其中 $$$b_j$$$ 是计算机在第 $$$j$$$ 轮中获得的分数。
输入中所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
按照输入中出现的顺序打印所有测试用例的答案。
如果 Polycarpus 无法赢得比赛,则只需打印一行“-1”(不带引号)。在这种情况下,您不应该为该测试用例输出任何其他内容。否则,测试用例答案的第一行应包含一个整数 $$$d$$$ — 赢得游戏所需的最小可能按下“重置”按钮的次数。下一行应包含 $$$d$$$ 不同的整数 $$$r_1, r_2, \dots, r_d$$$ ($$$1 \le r_i < n$$$) - 回合数,在回合结束时,Polycarpus 必须按任意顺序按下“重置”按钮。如果 $$$d=0$$$ 则要么将测试用例答案的第二行留空,要么根本不打印第二行。
如果有多种可能的解决方案,请打印其中任何一个。
示例
输入 #1
3 4 17 1 3 5 7 3 5 7 9 11 17 5 2 8 2 4 6 1 2 7 2 5 4 6 3 3 5 1 7 4 2 5 3 6 17 6 1 2 7 2 5 1 7 4 2 5 3
输出 #1
0 2 2 4 -1
注意
在第二个测试用例中,如果人类在第二轮和第四轮后按下“重置”按钮,则游戏进行如下:
1. 第一轮结束后,人类获得 $$$5$$$ 分,计算机 — $$$4$$$ 分;
2. 第二轮结束后,人类有 $$$7$$$ 分,计算机 — $$$10$$$ 分;
3. 人类按下“重置”按钮,现在他有 $$$0$$$ 点,计算机 — $$$3$$$ 点;
4. 第三轮结束后,人类有 $$$8$$$ 分,计算机 — $$$6$$$ 分;
5. 第四轮结束后,人类有 $$$10$$$ 分,计算机 — $$$9$$$ 分;
6. 人类再次按下“重置”按钮,之后他有 $$$1$$$ 点,计算机 — $$$0$$$ 点;
7. 第五轮结束后,人类有 $$$5$$$ 分,计算机 — $$$5$$$ 分;
8. 第六轮结束后,人类有 $$$11$$$ 分,计算机 — $$$6$$$ 分;
9. 第七轮结束后,人类有 $$$12$$$ 分,计算机 — $$$13$$$ 分;
10. 第八轮后,人类有 $$$14$$$ 分,计算机 — $$$17$$$ 分;
11. 人类获胜,因为计算机拥有 $$$k$$$ 或更多点,而人类 — 严格少于 $$$k$$$ 点。