Alan a reçu de Bekzhan un cadeau inhabituel pour son anniversaire. Le cadeau était protégé par un cadenas mathématique.

Le cadenas contient $N$ nombres, dont les positions sont numérotées de $1$ à $N$. Initialement, ils sont tous égaux à zéro. En une opération, Alan peut choisir un entier $X$ ($1\le X$) et $K$ positions distinctes du cadenas $1\le i_1,i_2,\ldots,i_K\le N$, puis ajouter $X$ à toutes les valeurs aux positions $i_1,i_2,\ldots,i_K$. Bekzhan lui a également indiqué la suite de nombres qui ouvre le cadenas : $A_1,A_2,\ldots,A_N$. L'ordre des nombres est important.

Alan n'arrive pas à résoudre ce problème. Aidez-le à ouvrir le cadenas ou déterminez qu'il n'existe aucune solution.

Vous n'avez pas besoin de minimiser le nombre d'opérations. Cependant, Alan ne veut pas sélectionner plus de $3000000$ ($3\cdot10^6$) positions au total. Autrement dit, si $M$ est le nombre d'opérations d'une solution, celle-ci est considérée comme correcte si $M\cdot K\le3\cdot10^6$, et incorrecte sinon.

Entrée

La première ligne contient deux entiers strictement positifs $N$ et $K$ ($2\le K\le N\le10^6$, $N\cdot K\le2\cdot10^6$) : la longueur de la suite du cadenas et le nombre de positions pouvant être choisies à chaque opération. La deuxième ligne contient $N$ entiers strictement positifs $A_1,A_2,\ldots,A_N$ ($1\le A_i$ pour tout $1\le i\le N$, $\sum_{i=1}^{N}A_i\le10^{18}$), séparés par une seule espace : la suite de nombres qui ouvre le cadenas.

Sortie

S'il n'existe aucune solution, affichez « -1 » (sans les guillemets). Sinon, affichez sur la première ligne $M$, le nombre d'opérations. Sur la $j$-ième des $M$ lignes suivantes, affichez $X_j$, puis $K$ nombres distincts $i_{j,1},i_{j,2},\ldots,i_{j,K}$ : la valeur ajoutée et les positions auxquelles cette valeur est ajoutée lors de la $j$-ième opération.

Sous-tâches

Ce problème comporte cinq sous-tâches. Dans chaque sous-tâche, les tests respectent les contraintes de l'énoncé :

1. $\sum_{i=1}^{N}A_i\le10$, $K=2$. 7 points.
2. $\sum_{i=1}^{N}A_i\le10^5$, $K=2$. 11 points.
3. $\sum_{i=1}^{N}A_i\le10^5$. 12 points.
4. $A_1=A_2=\cdots=A_N$. 19 points.
5. Les contraintes sont celles de l'énoncé. 51 points.

Exemples

Entrée 1

4 2
2 3 3 2

Sortie 1

3
2 3 1
1 3 2
2 2 4