Codeforces Round #416 (Div. 2) has been moved to start on 27.05.2017 09:35 (UTC).
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Education Reform

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYet 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...

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 *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.

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/26/2017 12:21:57 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|