Alan recebeu de Bekzhan um presente incomum de aniversário. O presente estava trancado com uma fechadura matemática.

A fechadura contém $N$ números, em posições numeradas de $1$ a $N$. Inicialmente, todos são iguais a zero. Em uma operação, Alan pode escolher um inteiro $X$ ($1\le X$) e $K$ posições distintas na fechadura, $1\le i_1,i_2,\ldots,i_K\le N$, e adicionar $X$ a todos os valores nas posições $i_1,i_2,\ldots,i_K$. Bekzhan também informou a sequência de números que abre a fechadura: $A_1,A_2,\ldots,A_N$. A ordem dos números é importante.

Alan não consegue resolver esse problema. Ajude-o a abrir a fechadura ou a determinar que não existe solução.

Observe que não é necessário minimizar o número de operações. Porém, Alan não quer selecionar mais de $3000000$ ($3\cdot 10^6$) posições no total, ou seja, se $M$ for o número de operações de uma solução e $M\cdot K\le 3\cdot 10^6$, a solução será considerada correta; caso contrário, não.

Entrada

A primeira linha da entrada contém dois inteiros positivos $N$ e $K$ ($2\le K\le N\le 10^6$, $N\cdot K\le 2\cdot 10^6$): o comprimento da sequência na fechadura e o número de posições que podem ser escolhidas em cada operação. A segunda linha contém $N$ inteiros positivos $A_1,A_2,\ldots,A_N$ ($1\le A_i$ para todo $1\le i\le N$, $\sum_{i=1}^N A_i\le 10^{18}$), separados por um único espaço: a sequência que abre a fechadura.

Saída

Se não existir solução, imprima -1 (sem aspas). Caso contrário, na primeira linha imprima $M$, o número de operações. Na $j$-ésima das próximas $M$ linhas, imprima $X_j$ e depois $K$ números distintos $i_{j,1},i_{j,2},\ldots,i_{j,K}$: o valor adicionado e as posições às quais esse valor é adicionado na $j$-ésima operação.

Pontuação

Este problema consiste em cinco subtarefas; em cada uma, os testes satisfazem as restrições do enunciado:

1. $\sum_{i=1}^N A_i\le 10$, $K=2$. Vale 7 pontos.
2. $\sum_{i=1}^N A_i\le 10^5$, $K=2$. Vale 11 pontos.
3. $\sum_{i=1}^N A_i\le 10^5$. Vale 12 pontos.
4. $A_1=A_2=\cdots=A_N$. Vale 19 pontos.
5. As restrições são as do enunciado. Vale 51 pontos.

Exemplos

Entrada 1

4 2
2 3 3 2

Saída 1

3
2 3 1
1 3 2
2 2 4