No tag edit access

C. Restore Graph

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputValera had an undirected connected graph without self-loops and multiple edges consisting of *n* vertices. The graph had an interesting property: there were at most *k* edges adjacent to each of its vertices. For convenience, we will assume that the graph vertices were indexed by integers from 1 to *n*.

One day Valera counted the shortest distances from one of the graph vertices to all other ones and wrote them out in array *d*. Thus, element *d*[*i*] of the array shows the shortest distance from the vertex Valera chose to vertex number *i*.

Then something irreparable terrible happened. Valera lost the initial graph. However, he still has the array *d*. Help him restore the lost graph.

Input

The first line contains two space-separated integers *n* and *k* (1 ≤ *k* < *n* ≤ 10^{5}). Number *n* shows the number of vertices in the original graph. Number *k* shows that at most *k* edges were adjacent to each vertex in the original graph.

The second line contains space-separated integers *d*[1], *d*[2], ..., *d*[*n*] (0 ≤ *d*[*i*] < *n*). Number *d*[*i*] shows the shortest distance from the vertex Valera chose to the vertex number *i*.

Output

If Valera made a mistake in his notes and the required graph doesn't exist, print in the first line number -1. Otherwise, in the first line print integer *m* (0 ≤ *m* ≤ 10^{6}) — the number of edges in the found graph.

In each of the next *m* lines print two space-separated integers *a*_{i} and *b*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*; *a*_{i} ≠ *b*_{i}), denoting the edge that connects vertices with numbers *a*_{i} and *b*_{i}. The graph shouldn't contain self-loops and multiple edges. If there are multiple possible answers, print any of them.

Examples

Input

3 2

0 1 1

Output

3

1 2

1 3

3 2

Input

4 2

2 0 1 3

Output

3

1 3

1 4

2 3

Input

3 1

0 0 0

Output

-1

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2017 16:28:57 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|