Problem: When you were a child you must have been told a puzzle of bags and coins. Anyway, here's one of its versions: 

A horse has three bags. The first bag has one coin, the second bag has one coin and the third bag has three coins. In total, the horse has three coins in the bags. How is that possible?

The answer is quite simple. The third bag contains a coin and two other bags. 

This problem is a generalization of the childhood puzzle. You have n bags. You know that the first bag contains a1 coins, the second bag contains a2 coins, ..., the n-th bag contains an coins. In total, there are s coins. Find the way to arrange the bags and coins so that they match the described scenario or else state that it is impossible to do.

Input

The first line contains two integers n and s (1 ≤ n, s ≤ 70000) — the number of bags and the total number of coins. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 70000), where ai shows the number of coins in the i-th bag.

Output

If the answer doesn't exist, print -1. 

Otherwise, print n lines, on the i-th line print the contents of the i-th bag. The first number in the line, ci (0 ≤ ci ≤ ai), must represent the number of coins lying directly in the i-th bag (the coins in the bags that are in the i-th bag are not taken into consideration). The second number in the line, ki (0 ≤ ki < n) must represent the number of bags that lie directly in the i-th bag (the bags that are inside the bags lying in the i-th bag are not taken into consideration). Next, the line must contain ki integers — the numbers of the bags that are lying directly in the i-th bag.

The total number of coins in the solution must equal s. If we count the total number of coins the i-th bag in the solution has, we should get ai. 

No bag can directly lie in more than one bag. The bags can be nested in more than one level (see the second test case). If there are multiple correct answers, you can print any of them.

Examples

Input

3 3
1 3 1


Output

1 0
1 2 3 1
1 0


Input

3 3
1 3 1


Output

1 0
2 1 3
0 1 1


Input

1 2
1


Output

-1


Input

8 10
2 7 3 4 1 3 1 2


Output

2 0
1 2 1 4
0 2 7 8
0 2 5 6
1 0
3 0
1 0
2 0

Note

The pictures below show two possible ways to solve one test case from the statement. The left picture corresponds to the first test case, the right picture corresponds to the second one.

<image>

Solution (in JAVA):

Solution:

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Set;

public class BagsAndCoins {
	//first[i] = j -> first j such that sum = i is possible
	static int[] first;
	//bit compressed boolean[] -- dp[i][j] = 1 if possible to make j with arr[0->i]
	static int[] dp;
	static boolean possible;
	static Set<Integer> indices;

	static int n;
	static int s;
	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);

		n = in.nextInt();
		s = in.nextInt();

		Bag[] unsorted = new Bag[n];
		Bag[] aa = new Bag[n];
		for(int i=0;i<n;i++) {
			unsorted[i] = new Bag(i, in.nextInt());
			aa[i] = new Bag(i, unsorted[i].cap);
		}
		
		Arrays.sort(aa, new Comparator<Bag>(){
			@Override
			public int compare(Bag o1, Bag o2) {
				return o1.cap - o2.cap;
			}
		});

		int target = s - aa[n-1].cap;
		Bag[] items = new Bag[n-1];
		for(int i =0;i<n-1;i++){items[i] = aa[i];} 

		solveKnapsack(target, items);
		if(!possible) {
			out.println(-1);
			out.close();
			return;
		} 
		
		int[] child = new int[n];
		Arrays.fill(child, -1);
		Bag[] rem = new Bag[n - indices.size()];
		int remSize =0;
		for(int i=0;i<n;i++) {
			if(!indices.contains(i)) {
				rem[remSize++] = unsorted[i];
			}
		}
		
		Arrays.sort(rem, new Comparator<Bag>(){
			@Override
			public int compare(Bag o1, Bag o2) {
				return o1.cap - o2.cap;
			}
		});
		
		for(int i=0;i<rem.length-1;i++) {
			child[rem[i+1].id] = rem[i].id; 
		}
		
		for(int i = 0; i < aa.length; i++) {
			if(indices.contains(i)) {
				out.println(unsorted[i].cap + " " + 0);
			} else {
				if(child[i] == -1) {
					out.println(unsorted[i].cap + " " + 0);
				} else {
					out.println(unsorted[i].cap - unsorted[child[i]].cap + " " + 1 + " " + (child[i]+1));
				}
			}
		}
		
		out.close();
	}

	static int MAX = 70001;
	static void solveKnapsack(int target, Bag[] items) {
		if(target < 0) {
			possible = false;
			return;
		}
		
		first = new int[MAX];
		Arrays.fill(first, -1);
		first[0] = 0;

		//dp[i] & (1<<(31-j)) = is sum = i*32 + j possible
		dp = new int[MAX / 32 + 1];
		dp[0] = 1<<31;
		for(int i = 0; i < items.length; i++) {
			for(int j = dp.length-1; j >= 0; j--) {
				int bucketlval = j * 32;
				int bucketrval = bucketlval + 31;
				//for this bucket, i am going to | with
				int orlval = bucketlval - items[i].cap;
				int orrval = bucketrval - items[i].cap;
				if(orrval < 0) continue;
				
				int oldAns = dp[j];
				
				if(orlval >= 0 && orlval % 32 == 0) {
					dp[j] |= dp[orlval / 32];
				} else {
					if(orlval < 0) {
						int numBit = orrval + 1;
						dp[j] |= (dp[0] >>> (32- numBit));
					} else {
						int numLeftBit = 32 - (orlval  % 32);
						int numRightBit = 32 - numLeftBit;
						int leftBucket = orlval / 32;
						int rightBucket = leftBucket+1;
						int ans = 0;
						ans |= dp[leftBucket] << numRightBit;
						if(rightBucket < dp.length) {
							ans |= (dp[rightBucket] >>> numLeftBit);
						}
						dp[j] |= ans;
					}
				}

				if(dp[j] != oldAns) {
					int changes = oldAns ^ dp[j];
					for(int k = 0; k < 32; k++) {
						if(((1<<(31-k)) & changes) != 0) {
							if(bucketlval + k < MAX)
								first[bucketlval + k] = i;
						}
					}
				}
			}
		}

		if(isPossible(target, dp)) {
			possible = true;
			indices = new HashSet();

			int curTarget = target;
			while(curTarget != 0) {
				indices.add(items[first[curTarget]].id);
				curTarget -= items[first[curTarget]].cap;
			}
		} else {
			possible = false;
		}
	}
	
	static boolean isPossible(int target, int[] dp) {
		return (dp[target / 32] & (1<<(31-(target % 32)))) != 0;
	}
	
	static void printDp() {
		for(int i = 0; i <= 10; i++) {
			System.out.println(i + " " + isPossible(i, dp));
		}
	}

	static class Bag {
		int id;
		int cap;
		public Bag(int id, int cap) {
			this.id = id;
			this.cap = cap;
		}
	}
	
	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}


		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}


		public String nextToken() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}

		public static boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}