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