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.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 * @author pttrung
 */
public class C_Round_90 {

    public static long MOD = 1000000007;
    static long[][][] dp;
    static HashMap<Long, Integer> map = new HashMap();
    static ArrayList<Long> list;
    static int n, m;
    static int[] next;

    public static void main(String[] args) throws FileNotFoundException {
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
        // "output.txt")));
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner();
        n = in.nextInt();
        m = in.nextInt();
        long k = in.nextInt();
        long[][] data = new long[m][4];
        TreeSet<Long> set = new TreeSet();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                data[i][j] = in.nextLong();
            }
            for (long j = data[i][0]; j <= data[i][1]; j++) {
                set.add(j);
            }
            data[i][3] = i;
        }

        list = new ArrayList();
        for (long i : set) {
            map.put(i, list.size());
            list.add(i);
        }
        Arrays.sort(data, new Comparator<long[]>() {
            @Override
            public int compare(long[] a, long[] b) {
                return Long.compare(a[2], b[2]);
            }

        }
        );
        next = new int[m];
        Arrays.fill(next, m);
        for (int i = m - 2; i >= 0; i--) {
            if (data[i][2] < data[i + 1][2]) {
                next[i] = i + 1;
            } else {
                next[i] = next[i + 1];
            }
        }

        dp = new long[m][n + 1][list.size()];

        for (long[][] b : dp) {
            for (long[] c : b) {
                Arrays.fill(c, -1);
            }
        }

        long v = cal(0, n, 0, k, data);
        // out.println(v);

        if (v >= 0) {
            out.println("YES");
            int index = 0;
            int left = n;
            int val = 0;

            while (left > 0) {
                // System.out.println(index + " " + left + " " + last + " " + num + " " + (dp[index][left][last][num]));
                if (index + 1 < m && dp[index][left][val] == dp[index + 1][left][val]) {
                    index++;
                } else if (left == n) {
                    for (long i = data[index][0]; i <= data[index][1]; i++) {
                        if (dp[index][left][val] == i + (next[index] < m ? dp[next[index]][left - 1][map.get(i)] : 0) && (next[index] == m || dp[next[index]][left - 1][map.get(i)] >= 0)) {
                            out.println((data[index][3] + 1) + " " + (i));
                            left--;
                            val = map.get(i);
                            index = next[index];
                            break;
                        }
                    }
                } else {
                    long tmp = list.get(val);
                    if (data[index][0] <= tmp + k && data[index][1] >= tmp + k) {
                        int nxt = map.get(tmp + k);
                        if ((next[index] == m || dp[next[index]][left - 1][nxt] >= 0) && (next[index] < m ? dp[next[index]][left - 1][nxt] : 0) + tmp + k == dp[index][left][val]) {
                            out.println((data[index][3] + 1) + " " + (tmp + k));
                            left--;
                            val = nxt;
                            index = next[index];
                            continue;
                        }
                    }
                    int nxt = map.get(tmp * k);
                    out.println((data[index][3] + 1) + " " + (tmp * k));
                    left--;
                    val = nxt;
                    index = next[index];

                }
            }
        } else {
            out.println("NO");
        }
        out.close();
    }

    public static long cal(int index, int left, int v, long k, long[][] data) {
        if (left == 0) {
            if (index < m) {
                dp[index][left][v] = 0;
            }
            return 0;
        }
        if (m - index < left) {
            return -2;
        }

        if (dp[index][left][v] != -1) {
            return dp[index][left][v];
        }
        long result = -2;

        if (left == n) {

            for (long i = data[index][1]; i >= data[index][0]; i--) {

                // System.out.println((data[index][3] + 1) + "  " + (data[index][0] + i));
                int tmp = map.get(i);
                long val = cal(next[index], left - 1, tmp, k, data);
                if (val >= 0) {
                    result = max(result, val + i);
                    if (k == 1) {
                        break;
                    }
                }
            }
        } else {

            long tmp = list.get(v);
            if (data[index][0] <= tmp + k && data[index][1] >= tmp + k) {

                long val = cal(next[index], left - 1, map.get(tmp + k), k, data);
                if (val >= 0) {
                    result = max(result, tmp + k + val);
                }
            }
            if (data[index][0] <= k * tmp && k * tmp <= data[index][1]) {

                long val = cal(next[index], left - 1, map.get(k * tmp), k, data);
                if (val >= 0) {
                    result = max(result, tmp * k + val);
                }
            }
        }

        result = max(result, cal(index + 1, left, v, k, data));

        return dp[index][left][v] = result;

    }

    static long max(long a, long b) {
        return a > b ? a : b;
    }

    public static int[] KMP(String val) {
        int i = 0;
        int j = -1;
        int[] result = new int[val.length() + 1];
        result[0] = -1;
        while (i < val.length()) {
            while (j >= 0 && val.charAt(j) != val.charAt(i)) {
                j = result[j];
            }
            j++;
            i++;
            result[i] = j;
        }
        return result;

    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static int digit(long n) {
        int result = 0;
        while (n > 0) {
            n /= 10;
            result++;
        }
        return result;
    }

    public static double dist(long a, long b, long x, long y) {
        double val = (b - a) * (b - a) + (x - y) * (x - y);
        val = Math.sqrt(val);
        double other = x * x + a * a;
        other = Math.sqrt(other);
        return val + other;

    }

    public static class Point implements Comparable<Point> {

        int x, y;

        public Point(int start, int end) {
            this.x = start;
            this.y = end;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 47 * hash + this.x;
            hash = 47 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }

        @Override
        public int compareTo(Point o) {
            return x - o.x;
        }
    }

    public static class FT {

        long[] data;

        FT(int n) {
            data = new long[n];
        }

        public void update(int index, long value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public long get(int index) {
            long result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long pow(long a, long b, long MOD) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2, MOD);
        if (b % 2 == 0) {
            return val * val % MOD;
        } else {
            return val * (val * a % MOD) % MOD;

        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //  br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}