C. Дифференциальная сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ элементов.

Вы можете выполнить следующую операцию не более $$$n$$$ раз: выбрать три индекса $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$ и заменить $$$a_x$$$ на $$$a_y - a_z$$$. После операции $$$|a_x|$$$ должно быть меньше $$$10^{18}$$$.

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

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

Каждый тест содержит несколько тестовых случаев. Первая строка будет содержать единственное целое число $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — количество тестов. Затем следуют $$$t$$$ тестовых случаев.

Первая строка каждого теста содержит одно целое число $$$n$$$ $$$(3 \leq n \leq 2 \cdot 10^5)$$$ — размер массива $$$a$$$.

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

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

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

Для каждого теста выведите $$$-1$$$, если решения нет. В противном случае в первой строке выведите единственное целое число $$$m$$$ $$$(0 \leq m \leq n)$$$ — количество выполненных вами операций.

Тогда $$$i$$$-я из следующих $$$m$$$ строк должна содержать три целых числа $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$— описание $$$i$$$-й операции.

Если решений несколько, можно вывести любое. Обратите внимание, что вам не нужно минимизировать количество операций в этой задаче.

Пример
Входные данные
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
Выходные данные
2
1 2 3
3 4 5
-1
0
Примечание

В первом примере массив становится

$$$[-6,-4,2,-1,2]$$$ после первой операции,

$$$[-6,-4,-3,-1,2]$$$ после второй операции.

Во втором примере невозможно сделать массив отсортированным ни после какой последовательности операций.

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