Problem: Yet another education system reform has been carried out in Berland recently. The innovations are as follows:

An academic year now consists of n days. Each day pupils study exactly one of m subjects, besides, each subject is studied for no more than one day. After the lessons of the i-th subject pupils get the home task that contains no less than ai and no more than bi exercises. Besides, each subject has a special attribute, the complexity (ci). A school can make its own timetable, considering the following conditions are satisfied:

  * the timetable should contain the subjects in the order of the complexity's strict increasing; 
  * each day, except for the first one, the task should contain either k times more exercises, or more by k compared to the previous day (more formally: let's call the number of home task exercises in the i-th day as xi, then for each i (1 < i ≤ n): either xi = k + xi - 1 or xi = k·xi - 1 must be true); 
  * the total number of exercises in all home tasks should be maximal possible. 



All limitations are separately set for each school.

It turned out that in many cases ai and bi reach 1016 (however, as the Berland Minister of Education is famous for his love to half-measures, the value of bi - ai doesn't exceed 100). That also happened in the Berland School №256. Nevertheless, you as the school's principal still have to work out the timetable for the next academic year...

Input

The first line contains three integers n, m, k (1 ≤ n ≤ m ≤ 50, 1 ≤ k ≤ 100) which represent the number of days in an academic year, the number of subjects and the k parameter correspondingly. Each of the following m lines contains the description of a subject as three integers ai, bi, ci (1 ≤ ai ≤ bi ≤ 1016, bi - ai ≤ 100, 1 ≤ ci ≤ 100) — two limitations to the number of exercises on the i-th subject and the complexity of the i-th subject, correspondingly. Distinct subjects can have the same complexity. The subjects are numbered with integers from 1 to m. 

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin stream or the %I64d specificator.

Output

If no valid solution exists, print the single word "NO" (without the quotes). Otherwise, the first line should contain the word "YES" (without the quotes) and the next n lines should contain any timetable that satisfies all the conditions. The i + 1-th line should contain two positive integers: the number of the subject to study on the i-th day and the number of home task exercises given for this subject. The timetable should contain exactly n subjects.

Examples

Input

4 5 2
1 10 1
1 10 2
1 10 3
1 20 4
1 100 5


Output

YES
2 8
3 10
4 20
5 40


Input

3 4 3
1 3 1
2 4 4
2 3 3
2 2 2


Output

NO

Solution (in JAVA):

Solution:
import java.util.NavigableSet;
import java.util.Map;
import java.util.Collections;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.math.BigInteger;
import java.util.*;
import java.util.Collection;
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.io.*;
import java.util.Iterator;
import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * Generated by Contest helper plug-in
 * Actual solution is at the bottom
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new StreamInputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		run(in, out);
	}

	public static void run(InputReader in, PrintWriter out) {
		Solver solver = new TaskC();
		solver.solve(1, in, out);
		Exit.exit(in, out);
	}
}

abstract class InputReader {
	private boolean finished = false;

	public abstract int read();

	public int readInt() {
		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 readLong() {
		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 readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuffer res = new StringBuffer();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public void setFinished(boolean finished) {
		this.finished = finished;
	}

	public abstract void close();
}

class StreamInputReader extends InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar, numChars;

	public StreamInputReader(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 void close() {
		try {
			stream.close();
		} catch (IOException ignored) {
		}
	}
}

class Exit {
	private Exit() {
	}

	public static void exit(InputReader in, PrintWriter out) {
		in.setFinished(true);
		in.close();
		out.close();
	}
}

interface Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out);
}

class ArrayUtils {

	public static void fill(long[][] array, long value) {
		for (long[] row : array)
			Arrays.fill(row, value);
	}

	public static void fill(long[][][] array, long value) {
		for (long[][] row : array)
			fill(row, value);
	}

	}

class CollectionUtils {

	public static<T extends Comparable<T>> T maxElement(Iterable<T> collection) {
		T result = null;
		for (T element : collection) {
			if (result == null || result.compareTo(element) < 0)
				result = element;
		}
		return result;
	}

	}

abstract class ReadOnlyIterator<T> implements Iterator<T>  {
	public final void remove() {
		throw new UnsupportedOperationException();
	}
}

abstract class AbstractSequence<T> implements Sequence<T> {

	public Iterator<T> iterator() {
		return new ReadOnlyIterator<T>() {
			private int index = 0;

			public boolean hasNext() {
				return index != size();
			}

			public T next() {
				if (!hasNext())
					throw new NoSuchElementException();
				return get(index++);
			}
		};
	}

	}

abstract class AbstractWritableSequence<T> extends AbstractSequence<T> implements WritableSequence<T> {

	}

abstract class ArrayWrapper<T> extends AbstractWritableSequence<T> {

	public static WritableSequence<Long> wrap(long...array) {
		return new LongArrayWrapper(array);
	}

	protected static class LongArrayWrapper extends ArrayWrapper<Long> {
		protected final long[] array;

		protected LongArrayWrapper(long[] array) {
			this.array = array;
		}

		public int size() {
			return array.length;
		}

		public Long get(int index) {
			return array[index];
		}

		}

	}

interface Sequence<T> extends Iterable<T> {
	public int size();
	public T get(int index);
}

class MiscUtils {

	public static<T> boolean equals(T first, T second) {
		return first == null && second == null || first != null && first.equals(second);
	}

	}

class SequenceUtils {
	public static<T> int find(Sequence<T> sequence, T value) {
		int size = sequence.size();
		for (int i = 0; i < size; i++) {
			if (MiscUtils.equals(sequence.get(i), value))
				return i;
		}
		return -1;
	}

	public static<T extends Comparable<T>> int maxIndex(Sequence<T> sequence) {
		return find(sequence, CollectionUtils.maxElement(sequence));
	}

	}

interface WritableSequence<T> extends Sequence<T> {
	}

class IOUtils {

	public static void readLongArrays(InputReader in, long[]... arrays) {
		for (int i = 0; i < arrays[0].length; i++) {
			for (int j = 0; j < arrays.length; j++)
				arrays[j][i] = in.readLong();
		}
	}

	}

class TaskC implements Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
		int dayCount = in.readInt();
		int studyCount = in.readInt();
		int delta = in.readInt();
		long[] min = new long[studyCount];
		long[] max = new long[studyCount];
		long[] hardness = new long[studyCount];
		IOUtils.readLongArrays(in, min, max, hardness);
		long[][][] total = new long[dayCount][studyCount][101];
		long[][][] last = new long[dayCount][studyCount][101];
		ArrayUtils.fill(total, Long.MIN_VALUE / 2);
		for (int i = 0; i < studyCount; i++) {
			for (int j = 0; j <= max[i] - min[i]; j++)
				total[0][i][j] = min[i] + j;
		}
		for (int i = 1; i < dayCount; i++) {
			for (int j = 0; j < studyCount; j++) {
				for (int k = 0; k <= max[j] - min[j]; k++) {
					for (int l = 0; l < studyCount; l++) {
						if (hardness[l] >= hardness[j])
							continue;
						long index = min[j] + k - delta - min[l];
						if (index >= 0 && index <= max[l] - min[l]) {
							long value = total[i - 1][l][((int) index)] + k + min[j];
							if (value > total[i][j][k]) {
								total[i][j][k] = value;
								last[i][j][k] = l + (index << 7);
							}
						}
						index = min[j] + k;
						if (index % delta != 0)
							continue;
						index = index / delta - min[l];
						if (index >= 0 && index <= max[l] - min[l]) {
							long value = total[i - 1][l][((int) index)] + k + min[j];
							if (value > total[i][j][k]) {
								total[i][j][k] = value;
								last[i][j][k] = l + (index << 7);
							}
						}
					}
				}
			}
		}
		long result = -1;
		long[][] longs = total[dayCount - 1];
		int lastStudy = -1;
		int count = -1;
		for (int i = 0, longsLength = longs.length; i < longsLength; i++) {
			long[] row = longs[i];
			int index = SequenceUtils.maxIndex(ArrayWrapper.wrap(row));
			if (row[index] > result) {
				result = row[index];
				lastStudy = i;
				count = index;
			}
		}
		if (result < 0) {
			out.println("NO");
			return;
		}
		int[] index = new int[dayCount];
		long[] homework = new long[dayCount];
		for (int i = dayCount - 1; i >= 0; i--) {
			index[i] = lastStudy + 1;
			homework[i] = min[lastStudy] + count;
			int nextStudy = (int) (last[i][lastStudy][count] & 127);
			int nextCount = (int) (last[i][lastStudy][count] >> 7);
			lastStudy = nextStudy;
			count = nextCount;
		}
		out.println("YES");
		for (int i = 0; i < dayCount; i++)
			out.println(index[i] + " " + homework[i]);
	}
}