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

The first line contains three integers $ n $ , $ m $ , $ k $ ( $ 1

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.