Alan отримав від Bekzhan незвичайний подарунок на день народження. Подарунок був замкнений на математичний замок.

Замок містить $N$ чисел, позиції яких пронумеровано від $1$ до $N$. Спочатку всі вони дорівнюють нулю. За одну операцію Alan може вибрати ціле число $X$ ($1 \le X$) та $K$ різних позицій замка $1 \le i_1,i_2,\ldots,i_K \le N$, а потім додати $X$ до всіх значень на позиціях $i_1,i_2,\ldots,i_K$. Bekzhan також повідомив послідовність чисел, що відкриває замок: $A_1,A_2,\ldots,A_N$. Порядок чисел важливий.

Alan не може впоратися із цією задачею. Допоможіть йому відкрити замок або визначити, що розв'язку не існує.

Зверніть увагу, що мінімізувати кількість операцій не потрібно. Проте Alan не хоче вибирати загалом більше ніж $3000000$ ($3\cdot10^6$) позицій. Тобто, якщо $M$ — кількість операцій у розв'язку та $M\cdot K \le 3\cdot10^6$, то розв'язок вважається правильним, інакше — ні.

Вхідні дані

Перший рядок містить два додатні цілі числа $N$ і $K$ ($2 \le K \le N \le 10^6$, $N\cdot K \le 2\cdot10^6$) — довжину послідовності в замку та кількість позицій, які можна вибрати за одну операцію. Другий рядок містить $N$ додатних цілих чисел $A_1,A_2,\ldots,A_N$ ($1 \le A_i$ для всіх $1 \le i \le N$, $\sum_{i=1}^{N} A_i \le 10^{18}$), розділених одним пробілом, — послідовність чисел, що відкриває замок.

Вихідні дані

Якщо розв'язку не існує, виведіть -1. Інакше в першому рядку виведіть $M$ — кількість операцій. У $j$-му з наступних $M$ рядків виведіть $X_j$, а потім $K$ різних чисел $i_{j,1},i_{j,2},\ldots,i_{j,K}$ — значення, яке додається, та позиції, до яких воно додається під час $j$-ї операції.

Підзадачі

Задача складається з п'яти підзадач; у кожній із них тести задовольняють обмеження з умови:

1. $\sum_{i=1}^{N} A_i \le 10$, $K=2$. 7 балів.
2. $\sum_{i=1}^{N} A_i \le 10^5$, $K=2$. 11 балів.
3. $\sum_{i=1}^{N} A_i \le 10^5$. 12 балів.
4. $A_1=A_2=\cdots=A_N$. 19 балів.
5. Обмеження з умови задачі. 51 бал.

Приклади

Вхідні дані 1

4 2
2 3 3 2

Вихідні дані 1

3
2 3 1
1 3 2
2 2 4