#P18129. Toilets
Toilets
Toilets
办公室是一条长度为 的圆,圆周上有若干厕所。每个员工都有一个预定时间 ,到时从圆周上坐标为 的工作位置出发,按给定方向以单位速度沿圆周行走,直到遇到一个空闲厕所并占用它。员工占用厕所的时长为 。
遇到已被占用的厕所时,员工会直接经过。如果多个员工同时到达同一个空闲厕所,则由开始行走时间更早的员工占用。输入保证 严格递增。前一个员工离开厕所的时刻,后一个员工可以立即占用该厕所。
请对每个员工求出其最终使用的厕所坐标,以及到达该厕所的时刻。
输入格式
第一行包含三个整数 ,满足
第二行包含 个整数 ,表示厕所所在坐标,满足
所有 互不相同。
接下来 行,每行描述一个员工,包含
满足
$$0\le t_i<10^{18},\quad 0\le p_i<L,\quad 1\le d_i\le10^{12},\quad t_i<t_{i+1}.$$字符 为 + 或 -,分别表示沿坐标增大的方向或沿坐标减小的方向移动。
所有输入均为整数。
输出格式
输出 行。第 行包含两个整数,表示第 个员工使用的厕所坐标和到达该厕所的时刻。
样例
5 3 45
10 20 30
0 0 + 200
2 5 + 10
20 40 - 100
21 16 + 10
50 0 + 22
20 20
10 7
30 30
10 60
10 105