Дан массив \(a\), состоящий из \(n\) положительных целых чисел, пронумерованных от \(1\) до \(n\). Вы можете выполнять с этим массивом следующую операцию не более \(3n\) раз:
- выбрать три целых числа \(i\), \(j\) и \(x\) (\(1 \le i, j \le n\); \(0 \le x \le 10^9\));
- присвоить \(a_i := a_i - x \cdot i\), \(a_j := a_j + x \cdot i\).
После каждой операции все элементы должны быть неотрицательными.
Можете ли вы задать такую последовательность из не более чем \(3n\) операций, после которой все элементы массива будут равны?
Выходные данные
Для каждого набора входных данных выведите ответ следующим образом:
- если описанной в условии последовательности операций не существует, выведите \(-1\);
- иначе выведите целое число \(k\) (\(0 \le k \le 3n\)) — количество операций, которые вы совершаете. Затем выведите \(k\) строк, \(m\)-я из которых должна содержать три целых числа \(i\), \(j\) и \(x\) (\(1 \le i, j \le n\); \(0 \le x \le 10^9\)) для \(m\)-й операции.
Если возможных последовательностей операций несколько, выведите любую из них. Обратите внимание, что минимизировать \(k\) не обязательно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3
|
2
4 1 2
2 3 3
-1
4
1 2 4
2 4 5
2 3 3
4 5 1
|