Education Reform

## 【题意】 有一所学校，这个学校一个学期有 $n$ 天，要学习 $m$ 门学科。每天都要学习一门学科，每个学科最多只能学习一天。 每门学科有 $3$ 个限制：$a_i,b_i,c_i$。 每天都要布置作业，每一天布置的作业量都有一定限制。 - 每天只能布置一科作业，且作业量保证在该学科的 $a_i,b_i$ 之间。 - 每天作业学科的 $c_i$ 值严格单调递增。 - 每一天的作业量 $x$ 都应该是前一天的作业量 $+k$ 或 $\times k$ （ $k$ 是定值） 求一种方案，使得总作业量最大（~~咳咳~~） ## 【输入格式】 第一行三个整数 $n, m, k$ ，具体意义见题目。 后面 $m$ 行，每行三个整数 $a_i,b_i,c_i$ 表示编号为　$i$ 的学科的三个指标。 ## 【输出格式】 第一行输出 `YES`或`NO` ，表示按这种性质是否每天都能有作业布置下来。 后面 $n$ 行每行输出两个整数，分别表示这天布置作业的学科编号与作业量。 ## 【数据范围】 $$ n,m \leq 50,k\leq 100 $$ $$ a_i\leq b_i\leq 10^{16},b_i-a_i\leq 100,c_i \leq 100 $$

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&lt;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.

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

YES
2 8
3 10
4 20
5 40

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

NO