办公室是一个长度为 $L$ 的圆环。办公室的不同位置设有若干个厕所。每位员工都有一个预定的时间 $t_i$，在此时刻，他们会从坐标为 $p_i$ 的工位起身，以单位速度沿预定方向在办公室中行走，直到找到一个可用的厕所，随后占用该厕所 $d_i$ 的时长。如果员工遇到一个已被占用的厕所，他们会直接经过。若多名员工同时到达一个可用的厕所，则由出发时间较早的员工占用（保证 $t_i$ 是单调递增的）。当上一位员工离开厕所时，下一位员工可以立即占用该厕所。

对于每位员工，求出他们将占用哪个厕所以及占用的时间。

输入格式

第一行包含三个数字 $n, m, L$ ($1 \le n, m \le 2 \cdot 10^5, 1 \le L \le 10^{12}$)，分别表示员工人数、厕所数量和办公室长度。

第二行包含 $m$ 个数字 $x_i$ ($0 \le x_i < L$)，表示厕所的坐标。保证所有 $x_i$ 互不相同。

接下来 $n$ 行描述员工信息，每行一个。每位员工由四个值 $t_i, p_i, s_i, d_i$ ($0 \le t_i < 10^{18}, 0 \le p_i < L, 1 \le d_i \le 10^{12}, t_i < t_{i+1}$) 描述。字符 $s_i$ 为 “+” 或 “-” （不含引号），分别表示第 $i$ 位员工沿坐标增加或减小的方向移动。保证所有输入数字均为整数。

输出格式

输出 $n$ 行，每行包含两个数字。第 $i$ 行应包含第 $i$ 位员工占用的厕所坐标以及占用该厕所的时间。

样例

输入 1

5 3 45
10 20 30
0 0 + 200
2 5 + 10
20 40 - 100
21 16 + 10
50 0 + 22

输出 1

20 20
10 7
30 30
10 60
10 105