#P18129. Toilets

Toilets

Toilets

办公室是一条长度为 LL 的圆,圆周上有若干厕所。每个员工都有一个预定时间 tit_i,到时从圆周上坐标为 pip_i 的工作位置出发,按给定方向以单位速度沿圆周行走,直到遇到一个空闲厕所并占用它。员工占用厕所的时长为 did_i。

遇到已被占用的厕所时,员工会直接经过。如果多个员工同时到达同一个空闲厕所,则由开始行走时间更早的员工占用。输入保证 tit_i 严格递增。前一个员工离开厕所的时刻,后一个员工可以立即占用该厕所。

请对每个员工求出其最终使用的厕所坐标,以及到达该厕所的时刻。

输入格式

第一行包含三个整数 n,m,Ln,m,L,满足

1≤n,m≤2⋅105,1≤L≤1012.1\le n,m\le2\cdot10^5,\qquad1\le L\le10^{12}.

第二行包含 mm 个整数 xix_i,表示厕所所在坐标,满足

0≤xi<L.0\le x_i<L.

所有 xix_i 互不相同。

接下来 nn 行,每行描述一个员工,包含

ti, pi, si, di,t_i,\ p_i,\ s_i,\ d_i,

满足

$$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}.$$

字符 sis_i 为 + 或 -,分别表示沿坐标增大的方向或沿坐标减小的方向移动。

所有输入均为整数。

输出格式

输出 nn 行。第 ii 行包含两个整数,表示第 ii 个员工使用的厕所坐标和到达该厕所的时刻。

样例

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