E. Сохраните сумму
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$k$$$ и массив $$$a$$$ длиной $$$n$$$, где каждый элемент удовлетворяет условию $$$0 \le a_i \le k$$$ для всех $$$1 \le i \le n$$$. Вы можете выполнить следующую операцию над массивом:

  • Выберите два различных индекса $$$i$$$ и $$$j$$$ ($$$1 \le i,j \le n$$$ и $$$i \neq j$$$) такие, что $$$a_i + a_j = k$$$.
  • Выберите целое число $$$x$$$, удовлетворяющее условию $$$-a_j \le x \le a_i$$$.
  • Уменьшите $$$a_i$$$ на $$$x$$$ и увеличьте $$$a_j$$$ на $$$x$$$. Другими словами, присвойте $$$a_i := a_i - x$$$ и $$$a_j := a_j + x$$$.

Обратите внимание, что ограничения на $$$x$$$ гарантируют, что все элементы массива $$$a$$$ остаются в пределах от $$$0$$$ до $$$k$$$ на протяжении всех операций.

Ваша задача — определить, возможно ли сделать массив $$$a$$$ неубывающим$$$^{\text{∗}}$$$ с помощью вышеуказанной операции. Если это возможно, найдите последовательность из не более чем $$$3n$$$ операций, которая преобразует массив в неубывающий.

Можно доказать, что если возможно сделать массив неубывающим с помощью вышеуказанной операции, существует решение, использующее не более чем $$$3n$$$ операций.

$$$^{\text{∗}}$$$ Массив $$$a_1, a_2, \ldots, a_n$$$ считается неубывающим, если для всех $$$1 \le i \le n - 1$$$ выполняется $$$a_i \le a_{i+1}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа, $$$n$$$ и $$$k$$$ ($$$4 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — длина массива $$$a$$$ и требуемая сумма для операции.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le k$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$-1$$$, если невозможно сделать массив неубывающим с помощью операции.

В противном случае выведите количество операций $$$m$$$ ($$$0 \le m \le 3n$$$). На каждой из следующих $$$m$$$ строк выведите три целых числа $$$i$$$, $$$j$$$ и $$$x$$$, представляющих операцию, где $$$a_i$$$ уменьшается на $$$x$$$, а $$$a_j$$$ увеличивается на $$$x$$$.

Обратите внимание, что вам не требуется минимизировать количество операций. Если есть несколько решений, требующих не более чем $$$3n$$$ операций, вы можете вывести любое из них.

Пример
Входные данные
4
5 100
1 2 3 4 5
5 6
1 2 3 5 4
5 7
7 1 5 3 1
10 10
2 5 3 2 7 3 1 8 4 0
Выходные данные
0
1
4 1 1
-1
6
1 8 2
3 5 2
5 7 3
5 9 3
8 10 5
2 10 4
Примечание

В первом наборе входных данных массив уже неубывающий, поэтому нам не нужно выполнять никаких операций.

Во втором наборе входных данных мы можем выполнить операцию с $$$i=4$$$, $$$j=1$$$ и $$$x=1$$$. $$$a_4$$$ уменьшается на $$$1$$$, становясь $$$5 - 1 = 4$$$, в то время как $$$a_1$$$ увеличивается на $$$1$$$, становясь $$$1 + 1 = 2$$$. После операции массив становится $$$[2, 2, 3, 4, 4]$$$ и является неубывающим.

Обратите внимание, что есть и другие способы сделать массив неубывающим, все из которых будут считаться правильными, если они не используют более чем $$$3 \cdot n = 15$$$ операций.

В третьем наборе входных данных невозможно сделать массив неубывающим. Это связано с тем, что нет различных пар индексов $$$i$$$ и $$$j$$$, где $$$a_i + a_j = 7$$$, поэтому никакая операция не может быть выполнена над массивом.

В четвертом наборе входных данных массив преобразуется следующим образом:

  1. $$$[\textbf{0}, 5, 3, 2, 7, 3, 1, \textbf{10}, 4, 0]$$$
  2. $$$[0, 5, \textbf{1}, 2, \textbf{9}, 3, 1, 10, 4, 0]$$$
  3. $$$[0, 5, 1, 2, \textbf{6}, 3, \textbf{4}, 10, 4, 0]$$$
  4. $$$[0, 5, 1, 2, \textbf{3}, 3, 4, 10, \textbf{7}, 0]$$$
  5. $$$[0, 5, 1, 2, 3, 3, 4, \textbf{5}, 7, \textbf{5}]$$$
  6. $$$[0, \textbf{1}, 1, 2, 3, 3, 4, 5, 7, \textbf{9}]$$$