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

最近，贝兰德（Berland）又进行了一次教育体制改革，具体改革内容如下：

一个学年现在由 $n$ 天组成。每天学生恰好学习 $m$ 门学科中的一门，且每门学科至多被安排在一天内讲授。第 $i$ 门学科授课后，学生需完成家庭作业，其中题量不少于 $a_i$ 道、不多于 $b_i$ 道。此外，每门学科还有一个特殊属性——难度值 $c_i$。学校可以自行制定课表，但必须满足以下条件：

• 课表中各学科的排列顺序必须严格按其难度值 $c_i$ 递增；
• 每天（除第一天外）的家庭作业题量，相比前一天，要么恰好增加 $k$ 道，要么恰好变为前一天的 $k$ 倍（更形式化地：设第 $i$ 天的家庭作业题量为 $x_i$，则对每个 $i$（$1 < i \leq n$），必须满足 $x_i = k + x_{i-1}$ 或 $x_i = k \cdot x_{i-1}$ 中的一个）；
• 所有家庭作业题量之和应尽可能大。

各项限制条件由各学校分别设定。

结果发现，在许多情况下，$a_i$ 和 $b_i$ 的取值可达 $10^{16}$（不过，由于贝兰德教育部长以“折中主义”闻名，故 $b_i - a_i$ 的值不超过 $100$）。贝兰德第 256 中学也正面临这一情况。然而，作为该校校长，你仍须为下一个学年制定出符合上述要求的最优课表……

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.

第一行包含三个整数 $n$、$m$、$k$（$1 ≤ n ≤ m ≤ 50$，$1 ≤ k ≤ 100$），分别表示学年的天数、科目的数量以及参数 $k$。接下来的 $m$ 行每行描述一门科目，包含三个整数 $a_i$、$b_i$、$c_i$（$1 ≤ a_i ≤ b_i ≤ 10^{16}$，$b_i - a_i ≤ 100$，$1 ≤ c_i ≤ 100$）—— 分别表示第 $i$ 门科目的习题数量下限与上限，以及该科目的难度。不同科目可以具有相同的难度。科目编号为 $1$ 到 $m$ 的整数。

在 C++ 中，请勿使用 %lld 格式说明符读写 64 位整数。推荐使用 cin 流或 %I64d 格式说明符。

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.

如果不存在合法解，则输出单个单词 “NO”（不带引号）。否则，第一行应输出单词 “YES”（不带引号），接下来的 $n$ 行应输出任意一个满足所有条件的时间表。第 $i+1$ 行应包含两个正整数：第 $i$ 天所学课程的编号，以及该课程布置的家庭作业题数。该时间表必须恰好包含 $n$ 门课程。