A8359 | Education Reform

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 $10^{16}$ (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}<=10^{16}$ , $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.