题目描述
实验室有m个登记窗口，编号为1到m。第i份样品在时刻送到，类别为，登记它需要单位时间。样品按输入顺序安排；输入已按到达时刻从小到大排列，到达时刻相同的也按输入顺序安排。
每个窗口最初空闲，并且没有登记过样品。一份样品必须按以下规则选择窗口：
- 如果在它到达的时刻有空闲窗口，选择编号最小的空闲窗口。
- 如果此时所有窗口都忙，则等到最早有窗口完成已安排的工作时，选择那一时刻空闲窗口中编号最小的一个。
选定窗口后，登记开始前还可能需要清洗：如果该窗口此前登记过样品，并且最近一次登记的样品类别与当前类别不同，就先清洗h单位时间。没有登记过样品，或者前后类别相同，都不清洗。窗口空闲多久都不会忘记上次登记的类别。
清洗与登记期间，该窗口都处于忙碌状态。一个窗口在时刻x完成登记，则在时刻x立即空闲；到达时刻也是x的样品可以使用它。清洗时间不参与窗口的选择：先按上述两条规则选定窗口，再判断是否清洗。
请依次输出每份样品使用的窗口编号，以及它完成登记的时刻。
输入格式
从文件desk.in读入数据。
第一行包含两个正整数n、m和一个非负整数h，分别表示样品数量、窗口数量和清洗所需时间。
接下来n行，第i行包含三个整数、、。
输出格式
输出到文件desk.out。
输出n行，第i行包含两个整数，分别是第i份样品使用的窗口编号和完成登记的时刻。
样例1
样例输入：
5 2 4
0 1 5
0 2 2
2 1 1
5 2 3
20 3 1
样例输出：
1 5
2 2
2 7
1 12
1 25
第3份样品到达时，2号窗口恰好空闲，需先清洗4单位时间，在时刻7完成。第5份样品到达时两个窗口都空闲，因此选择1号窗口，即使2号窗口上次完成得更早。
样例2
样例输入：
4 1 5
0 1 3
3 1 1
4 2 2
20 2 1
样例输出：
1 3
1 4
1 11
1 21
第2份样品不需清洗；第3份样品需清洗。第4份样品与此前类别相同，即使窗口已经空闲了一段时间，也不需清洗。
数据范围
对于所有测试数据：，，，，、。保证t_1 ≤ t_2 ≤ … ≤ t_n。
共20个测试点，每点5分，独立计分。
| 测试点 | 附加限制 |
|---|---|
| 1-4 | ，，，， |
| 5-8 | |
| 9-12 | |
| 13-16 | ，，， |
| 17-20 | 无附加限制 |