Вам дано целое число $$$k$$$ и массив $$$a$$$ длиной $$$n$$$, где каждый элемент удовлетворяет условию $$$0 \le a_i \le k$$$ для всех $$$1 \le i \le n$$$. Вы можете выполнить следующую операцию над массивом:
Обратите внимание, что ограничения на $$$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$$$ операций, вы можете вывести любое из них.
45 1001 2 3 4 55 61 2 3 5 45 77 1 5 3 110 102 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$$$, поэтому никакая операция не может быть выполнена над массивом.
В четвертом наборе входных данных массив преобразуется следующим образом:
| Codeforces Round 1019 (Div. 2) |
|---|
| Закончено |
