D. Рождество или истерия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Mass Hysteria (Hearthstone)
$$$\color{white}{\text{You are sus}}$$$

Франклин планирует рождественскую атаку, в которой он накладывает заклинание Массовая истерия на деревню эльфов.

В деревне $$$n$$$ эльфов, пронумерованных от $$$1$$$ до $$$n$$$, и у эльфа $$$i$$$ есть $$$h_i$$$ здоровья и $$$a_i$$$ атаки. Изначально $$$h_i=a_i$$$ для всех $$$i$$$, и все $$$a_i$$$ различны. Эльф $$$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$$$) — указывая, что эльф $$$x_i$$$ атакует эльфа $$$y_i$$$ на $$$i$$$-й итерации.

Последовательность должна удовлетворять всем следующим условиям:

  • Непосредственно перед $$$i$$$-й итерацией оба эльфа $$$x_i$$$ и $$$y_i$$$ живы, и эльф $$$x_i$$$ не атаковал в предыдущих итерациях.
  • После $$$k$$$-й итерации ровно $$$m$$$ эльфов живы, и не существует пары различных живых эльфов $$$x$$$ и $$$y$$$, такой что эльф $$$x$$$ не атаковал ранее.

Если существует несколько ответов, выведите любой из них. Любая допустимая последовательность, удовлетворяющая вышеуказанным условиям, будет принята.

Пример
Входные данные
7
4 2
1 4 2 3
2 2
6 7
3 0
1 2 3
3 1
1 2 3
3 2
1 2 3
4 1
2 3 4 5
6 0
998244353 1000000000 314159265 676767677 999999999 987654321
Выходные данные
2
3 1
2 4
-1
2
3 2
1 3
2
1 2
3 2
-1
2
1 4
4 2
4
3 1
2 5
6 1
4 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)$$$ для первой итерации.

В шестом наборе входных данных только эльф $$$3$$$ жив после всех атак. Хотя эльф $$$3$$$ не атаковал ранее, Массовая истерия завершается, так как ему некого атаковать.