Problem: Gleb is a famous competitive programming teacher from Innopolis. He is planning a trip to N programming camps in the nearest future. Each camp will be held in a different country. For each of them, Gleb needs to apply for a visa. 

For each of these trips Gleb knows three integers: the number of the first day of the trip si, the length of the trip in days leni, and the number of days ti this country's consulate will take to process a visa application and stick a visa in a passport. Gleb has P (1 ≤ P ≤ 2) valid passports and is able to decide which visa he wants to put in which passport.

For each trip, Gleb will have a flight to that country early in the morning of the day si and will return back late in the evening of the day si + leni - 1.

To apply for a visa on the day d, Gleb needs to be in Innopolis in the middle of this day. So he can't apply for a visa while he is on a trip, including the first and the last days. If a trip starts the next day after the end of the other one, Gleb can't apply for a visa between them as well. The earliest Gleb can apply for a visa is day 1.

After applying for a visa of country i on day d, Gleb will get his passport back in the middle of the day d + ti. Consulates use delivery services, so Gleb can get his passport back even if he is not in Innopolis on this day. Gleb can apply for another visa on the same day he received his passport back, if he is in Innopolis this day. 

Gleb will not be able to start his trip on day si if he doesn't has a passport with a visa for the corresponding country in the morning of day si. In particular, the passport should not be in another country's consulate for visa processing.

Help Gleb to decide which visas he needs to receive in which passport, and when he should apply for each visa. 

Input

In the first line of the input there are two integers N (1 ≤ N ≤ 22) and P (1 ≤ P ≤ 2)—the number of trips and the number of passports Gleb has, respectively.

The next N lines describe Gleb's trips. Each line contains three positive integers si, leni, ti (1 ≤ si, leni, ti ≤ 109)—the first day of the trip, the length of the trip and number of days the consulate of this country needs to process a visa application. It is guaranteed that no two trips intersect.

Output

If it is impossible to get all visas on time, just print "NO" (quotes for clarity). Otherwise, print "YES" and N lines describing trips. For each trip, first print number of the passport Gleb should put this country's visa in, and then print number of the day he should apply for it. Print trips in the same order as they appear in the input. Days are numbered from 1, starting with tomorrow—the first day you can apply for a visa. Passports are numbered from 1 to P.

If there are several possible answers, print any of them.

Examples

Input

2 1
3 1 1
6 1 1


Output

YES
1 1
1 4


Input

3 1
13 2 2
7 3 1
19 3 4


Output

YES
1 10
1 1
1 2


Input

7 2
15 1 1
14 1 1
18 1 1
21 1 1
9 4 6
22 2 5
5 4 3


Output

YES
2 13
1 1
1 16
1 19
1 2
2 16
2 1


Input

3 1
7 3 1
13 2 3
19 3 4


Output

NO

Note

Examples with answer "YES" are depicted below.

Each cell of the stripe represents a single day. Rectangles represent trips, each trip starts in the morning and ends in the evening. Rectangles with angled corners represent visa applications. Each application starts in the middle of a day and ends ti days after. The trip and the visa application for the same country have the same color.

In examples with two passports, visa applications and trips depicted above the time stripe are made using the first passport, visa applications and trips depicted below the time stripe are made using the second passport.

Example 1: 

<image>

Example 2: 

<image>

Example 3: 

<image>

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.stream.*;

public class F {

	static class Trip implements Comparable<Trip> {
		int from, to;
		int need;
		int id;
		public Trip(int from, int to, int need, int id) {
			this.from = from;
			this.to = to;
			this.need = need;
			this.id = id;
		}
		@Override
		public int compareTo(Trip o) {
			return Integer.compare(from, o.from);
		}
	}
	
	Trip[] a;
	int[] dp, last, lastStart;
	
	
	void submit() {
		int n = nextInt();
		int p = nextInt();
		a = new Trip[n];
		for (int i = 0; i < n; i++) {
			int s = nextInt();
			int len = nextInt();
			int need = nextInt();
			a[i] = new Trip(s, s + len, need, i);
		}
		
		Arrays.sort(a);
		
		dp = new int[1 << n];
		last = new int[1 << n];
		lastStart = new int[1 << n];
		
		Integer[] order = new Integer[n];
		for (int i = 0; i < n; i++) {
			order[i] = i;
		}
		
		Arrays.sort(order, Comparator.comparingInt(x -> a[x].need));
		
		Arrays.fill(dp, INF);
		dp[0] = 1;
		
		int[] wL = new int[n];
		int[] wR = new int[n];

		wL[0] = 1;
		for (int i = 0; i < n - 1; i++) {
			wL[i + 1] = a[i].to;
		}
		for (int i = 0; i < n; i++) {
			wR[i] = a[i].from;
		}
		
		for (int mask = 0; mask < 1 << n; mask++) {
			if (dp[mask] == INF) {
				continue;
			}
			
			int ptr = 0;
			int check = mask == 0 ? n : Integer.numberOfTrailingZeros(mask); 
			
			for (int add : order) {
				if (test(mask, add)) {
					continue;
				}
				while (ptr < n) {
					int start = Math.max(dp[mask], wL[ptr]);

					boolean advancePtr = false;
					
					if (start >= wR[ptr]) {
						advancePtr = true;
					} else if (check != n && start + a[add].need >= a[check].from) {
						advancePtr = true;
					} else {
						int newVal = start + a[add].need; 
						if (newVal < a[add].from) {
							if (dp[mask | (1 << add)] > newVal) {
								dp[mask | (1 << add)] = newVal;
								last[mask | (1 << add)] = add;
								lastStart[mask | (1 << add)] = start;
							}
						}
					}
					
					if (advancePtr) {
						if (ptr == check) {
							check++;
							while (check < n && !test(mask, check)) {
								check++;
							}
						}
						ptr++;
					} else {
						break;
					}

				}
			}
		}
		
		int[] ans1 = new int[n];
		int[] ans2 = new int[n];
		ans1[0] = -1;
		
		if (p == 1) {
			if (dp[(1 << n) - 1] < INF) {
				fillAns((1 << n) - 1, 1, ans1, ans2);
			}
		} else {
			for (int i = 0; i < 1 << n; i++) {
				if (dp[i] < INF && dp[((1 << n) - 1) ^ i] < INF) {
					fillAns(i, 1, ans1, ans2);
					fillAns(((1 << n) - 1) ^ i, 2, ans1, ans2);
					break;
				}
			}
		}
		
		if(ans1[0] == -1) {
			out.println("NO");
		} else {
			out.println("YES");
			for (int i = 0; i < n; i++) {
				out.println(ans1[i] + " " + ans2[i]);
			}
		}
	}
	
	void fillAns(int mask, int id, int[] ans1, int[] ans2) {
		while (mask > 0) {
			int x = last[mask];
			ans1[a[x].id] = id;
			ans2[a[x].id] = lastStart[mask];
			mask ^= (1 << x);
		}
	}
	
	static boolean test(int mask, int i) {
		return ((mask >> i) & 1) == 1;
	}
	
	static final int INF = Integer.MAX_VALUE / 2;

	void test() {

	}

	void stress() {
		for (int tst = 0;; tst++) {
			if (false) {
				throw new AssertionError();
			}
			System.err.println(tst);
		}
	}

	F() throws IOException {
		is = System.in;
		out = new PrintWriter(System.out);
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();
	static final int C = 5;

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new F();
	}

	private InputStream is;
	PrintWriter out;

	private byte[] buf = new byte[1 << 14];
	private int bufSz = 0, bufPtr = 0;

	private int readByte() {
		if (bufSz == -1)
			throw new RuntimeException("Reading past EOF");
		if (bufPtr >= bufSz) {
			bufPtr = 0;
			try {
				bufSz = is.read(buf);
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			if (bufSz <= 0)
				return -1;
		}
		return buf[bufPtr++];
	}

	private boolean isTrash(int c) {
		return c < 33 || c > 126;
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isTrash(b))
			;
		return b;
	}

	String nextToken() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	String nextString() {
		int b = readByte();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b) || b == ' ') {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	char nextChar() {
		return (char) skip();
	}

	int nextInt() {
		int ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}

	long nextLong() {
		long ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}
}