富兰克林正在策划一场圣诞节袭击,他在其中施展了咒语 集体歇斯底里 在一个精灵村庄。
有$$$n$$$个精灵,编号为$$$1$$$到$$$n$$$,其中精灵$$$i$$$的生命值为$$$h_i$$$,攻击值为$$$a_i$$$。 最初,对于所有 $$$i$$$,$$$h_i=a_i$$$ 且所有 $$$a_i$$$ 都是不同的。 Elf $$$i$$$ 还活着当且仅当其健康状况为正(即 $$$h_i \gt 0$$$)。
当富兰克林施放时 集体歇斯底里,重复以下过程:
- 选择一对不同的活着的精灵 $$$x$$$ 和 $$$y$$$ ($$$h_x,h_y \gt 0$$$) 使得精灵 $$$x$$$ 有 不 之前受到过攻击。如果不存在这样的对,则终止该过程。
- 然后,精灵$$$x$$$攻击精灵$$$y$$$,使$$$h_y$$$减少$$$a_x$$$。此外,由于反冲,$$$h_x$$$ 减少了$$$a_y$$$。请注意,$$$a_x$$$ 和 $$$a_y$$$ 保持不变。
该过程将重复,直到无法选择一对有效的精灵为止。可以证明 集体歇斯底里 最多在 $$$n$$$ 次迭代后终止。
给定一个整数$$$m$$$,构造一个有效的攻击序列,使得当进程结束时$$$m$$$精灵还活着;或确定不存在这样的序列。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\le n\le 2\cdot 10^5, 0\le m\le n$$$) — 村庄中的精灵数量和存活的精灵数量。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — 初始攻击 和 精灵的健康值。
保证所有 $$$a_i$$$ 都是不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10 ^ 5$$$。
输出
对于每个测试用例,如果 $$$m$$$ 精灵不可能存活,则打印 $$$-1$$$。
否则,输出有效的攻击序列,如下所示:
- 在第一行,输出一个整数 $$$k$$$ ($$$0\le k\le n$$$) — 中的迭代次数 集体歇斯底里.
- 接下来是 $$$k$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1\leq x_i,y_i\leq n$$$, $$$x_i\neq y_i$$$),表明 elf $$$x_i$$$ 攻击 elf第 $$$i$$$ 次迭代中的 $$$y_i$$$。
该序列必须满足以下所有条件:
- 在第 $$$i$$$ 次迭代之前,精灵 $$$x_i$$$ 和 $$$y_i$$$ 都活着,并且精灵 $$$x_i$$$ 在之前的任何迭代中都没有受到攻击。
- 在第 $$$k$$$ 次迭代之后,恰好 $$$m$$$ 精灵还活着,并且不存在一对不同的活着精灵 $$$x$$$ 和 $$$y$$$ 使得精灵 $$$x$$$ 之前没有攻击过。
如果有多个答案,则可以输出其中任何一个。任何满足上述条件的有效序列都将被接受。
示例
输入复制
74 21 4 2 32 26 73 01 2 33 11 2 33 21 2 34 12 3 4 56 0998244353 1000000000 314159265 676767677 999999999 987654321
输出复制
23 12 4-123 21 321 23 2-121 44 243 12 56 14 2
注意
在第一个测试用例中,一个可能的攻击序列如下所示:
| # | $$$x$$$ | $$$y$$$ | 攻击后的生命值 | 已攻击的精灵 |
| 0 | — | — | $$$[1, 4, 2, 3]$$$ | $$$[]$$$ |
| 1 | $$$3$$$ | $$$1$$$ | $$$[-1, 4, 1, 3]$$$ | $$$[3]$$$ |
| 2 | $$$2$$$ | $$$4$$$ | $$$[-1, 1, 1, -1]$$$ | $$$[2, 3]$$$ |
经过 $$$2$$$ 迭代后,只有精灵 $$$2$$$ 和 $$$3$$$ 还活着。由于他们都已经攻击过,不可能再进行有效的攻击,并且 集体歇斯底里 终止。
在第二个测试用例中,第一次迭代中 $$$(x,y)$$$ 的唯一可能选择是 $$$(1,2)$$$ 或 $$$(2,1)$$$。无论哪种情况,精灵 $$$1$$$ 最终都会获得 $$$-1$$$ 生命值,因此两个精灵最终都不可能都活着。请注意 集体歇斯底里 将持续至少一次迭代,因为第一次迭代存在有效的 $$$(x,y)$$$。
在第六个测试用例中,在所有攻击后,只有 elf $$$3$$$ 还活着。尽管精灵$$$3$$$之前没有攻击过, 集体歇斯底里 终止,因为没有其他精灵可以攻击。