C. Education Reform
time limit per test
1 second
memory limit per test
256 megabytes
standard input
standard output

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 a i and no more than b i exercises. Besides, each subject has a special attribute, the complexity ( c i). 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 x i, then for each i (1 < i ≤ n): either x i = k + x i - 1 or x i = k·x i - 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 a i and b i reach 1016 (however, as the Berland Minister of Education is famous for his love to half-measures, the value of b i - a i 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...


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 a i, b i, c i (1 ≤ a i ≤ b i ≤ 1016, b i - a i ≤ 100, 1 ≤ c i ≤ 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.


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.

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