Alan は誕生日に Bekzhan から珍しい贈り物をもらいました。その贈り物には数学的な錠がかかっていました。

錠には $N$ 個の数があり、その位置には $1$ から $N$ までの番号が付いています。初めはすべて $0$ です。1 回の操作で、Alan は整数 $X$ ($1\le X$) と、錠の異なる $K$ 個の位置 $1\le i_1,i_2,\ldots,i_K\le N$ を選び、位置 $i_1,i_2,\ldots,i_K$ の値すべてに $X$ を加えることができます。Bekzhan は錠を開ける数列 $A_1,A_2,\ldots,A_N$ も教えてくれました。数の順序は重要です。

Alan はこの問題を解けません。錠を開けるのを手伝うか、解が存在しないことを判定してください。

操作回数を最小化する必要はありません。ただし Alan は、選ぶ位置の総数を $3000000$ ($3\cdot10^6$) 以下にしたいと考えています。つまり、解の操作回数を $M$ とすると、$M\cdot K\le3\cdot10^6$ ならその解は正しく、そうでなければ正しくないとみなされます。

入力

入力の最初の行には、錠の数列の長さと各操作で選べる位置の数を表す 2 つの正整数 $N,K$ ($2\le K\le N\le10^6$, $N\cdot K\le2\cdot10^6$) が与えられます。2 行目には、錠を開ける数列を表す $N$ 個の正整数 $A_1,A_2,\ldots,A_N$ ($1\le A_i$ がすべての $1\le i\le N$ について成り立ち、$\sum_{i=1}^{N}A_i\le10^{18}$) が、1 個の空白で区切って与えられます。

出力

解が存在しない場合は、-1 を引用符なしで出力してください。それ以外の場合、最初の行に操作回数 $M$ を出力してください。続く $M$ 行のうち $j$ 行目には、$X_j$ に続けて異なる $K$ 個の数 $i_{j,1},i_{j,2},\ldots,i_{j,K}$ を出力してください。これらは、それぞれ $j$ 回目の操作で加える値と、その値を加える位置を表します。

小課題

この問題は 5 つの小課題からなり、各小課題のテストは問題文の制約を満たします。

1. $\sum_{i=1}^{N}A_i\le10$, $K=2$。7 点。
2. $\sum_{i=1}^{N}A_i\le10^5$, $K=2$。11 点。
3. $\sum_{i=1}^{N}A_i\le10^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