Alan received from Bekzhan unusual gift on birthday. The gift was locked under a mathematical lock.

Lock contains $N$ numbers, positions numbered from $1$ to $N$. Initially, all of them are equal to zero. In one operation Alan can choose some integer $X$ ($1 \le X$) and $K$ different positions in the lock $1 \le i_1, i_2, \ldots, i_K \le N$, then add $X$ to all values at positions $i_1, i_2, \ldots, i_K$. Bekzhan also reported the sequence of numbers which opens the lock — $A_1, A_2, \ldots, A_N$. Order of numbers is important.

Alan cannot handle this problem. Help him to unlock or determine that solution does not exist.

Note that you do not need to minimize number of operations. But Alan does not want to select more than 3000000 ($3 \cdot 10^6$) positions in total, i.e. if $M$ equals to the number of operations in a solution and $M \cdot K \le 3 \cdot 10^6$, then the solution is considered as correct, otherwise not.

Input

The first line of input contains two positive integer numbers $N$ and $K$ ($2 \le K \le N \le 10^6$, $N \cdot K \le 2 \cdot 10^6$) — length of the sequence in lock and number of positions, which can be chosen on each operation. The second line of input contains $N$ positive integer numbers $A_1, A_2, \ldots, A_N$ ($1 \le A_i$, for all $1 \le i \le N$, $\sum_{i=1}^{N} A_i \le 10^{18}$) separated with single space — sequence of numbers which opens the lock.

Output

If solution does not exist, output “−1” (without quotes). Otherwise, in the first line output $M$ — the number of operations. In $j$’th line of the next $M$ lines print $X_j$, then $K$ different numbers $i_{j,1}, i_{j,2}, \ldots, i_{j,K}$ — the added value and positions, to which the value is added on $j$’th operation.

Subtasks

This problem consists of five subtasks, in each subtask tests satisfy constraints in statement:

1. $\sum_{i=1}^{N} A_i \le 10$, $K = 2$. Score 7 points.
2. $\sum_{i=1}^{N} A_i \le 10^5$, $K = 2$. Score 11 points.
3. $\sum_{i=1}^{N} A_i \le 10^5$. Score 12 points.
4. $A_1 = A_2 = \ldots = A_N$. Score 19 points.
5. Constraints are from problem statement. Score 51 points.

Examples

Input 1

4 2
2 3 3 2

Output 1

3
2 3 1
1 3 2
2 2 4