Excalibur is the legendary sword of King Arthur, sometimes also attributed with magical powers or associated with the rightful sovereignty of Britain. In order to be the King of the Great Britain, Alan decided to craft Excalibur. There is some really old magic, that allows you to create the sword. There are m words in the magic spell, each word is represented by some integer wi. In order to cast the spell, you need to construct connected graph with n vertices and m edges without loops or multiple edges. Edge weights should be weights from the magic spell. In other words, weights of this graph should form permutation of wi. In this graph the sum of the edges of minimum spanning tree should be equal to X. Minimum spanning tree is the undirected connected graph with n - 1 edges without cycles, such that sum of the edges in this tree is minimum possible.

Input

On the first line you are given 3 integers n, m, X (2 ≤ n ≤ 100, 0 ≤ m ≤ 1000, 0 ≤ X ≤ 4000). In the second line you are given m integers wi(1 ≤ wi ≤ 40).

Output

If it is not possible to craft Excalibur, on the single line output -1. Otherwise, on the first line output m. On the next m lines output 3 integers on each, u, v, c (1 ≤ u ≤ n, 1 ≤ v ≤ n, u ≠ v, 1 ≤ c ≤ 40) – edges of the graph. Weights should be some permutation of wi from the input.