CF581E Kojiro and Furrari

汽车司机 Kojiro 花了 $10$ 年时间为他最喜欢的汽车品牌法拉利攒钱。终于，Kojiro 的梦想实现了！现在 Kojiro 想去找他的女友 Johanna，向她炫耀他的汽车。 Kojiro 希望赶到他女朋友那里，所以他将沿着一条坐标轴前往。为了方便起见，我们假设 Kojiro 在坐标线上的点 $f$ 处，而 Johanna 在点 $e$ 处。坐标轴上的一些点设有加油站。每个加油站只提供一种类型的燃料：$92$ 号汽油，$95$ 号汽油或 $98$ 号汽油。因此，每个加油站由一对整数 $t_i$ 和 $x_i$ 来描述，$t_i$ 表示燃料类型的编号，$x_i$ 表示加油站的位置。 一升燃料正好可以行驶 $1$ 千米（这个值与燃料类型无关）。三种类型的燃料仅在质量上有所不同，据研究表明，这影响发动机的寿命。一辆法拉利的油箱容量恰好为 $s$ 升（不管燃料类型如何）。在小次郎从点 $f$ 出发时，他的油箱已经完全装满了 $98$ 号汽油。在每个加油站，小次郎可以加满油箱，但当然，油箱中的燃油量在任何时间点都不能超过 $s$ 升。注意，油箱可以同时装有不同类型的燃料。汽车可以向左或向右两个方向移动。 为了延长发动机的使用寿命，Kijiro 主要希望最大限度地减少 $92$ 号汽油的使用量。如果有多种从点 $f$ 到点 $e$ 的方案使用最少量的 $92$ 号汽油，那么需要选择最小化使用 $95$ 号汽油的量的方案。 请编写一个程序，可以对于起始位置 $f_i$ 的 $m$ 个可能位置，首先最小化使用的 $92$ 号汽油的量，其次最小化使用的 $95$ 号汽油的量。 ### **简明题意** 对于在坐标轴上的 $m$ 个起点和一个终点，请找出每个起点在所有到终点的方案中，最小化 $92$ 号汽油，其次 $95$ 号汽油的方案。

输入的第一行包含四个正整数 $e,s,n,m$ $(1 \le e,s \le 10^9,1 \le n,m \le 2 \cdot 10^5)$，分别表示 Johanna 所在点的坐标，法拉利油箱容量，加油站数量和起点数量。 接下来的 $n$ 行，每行包含两个整数 $t_i,x_i$ $(1 \le t_i \le 3,-10^9 \le x_i \le 10^9)$，分别表示第 $i$ 个加油站的类型（ $1$ 代表 $Regular-92$，$2$ 代表 $Premium-95$，$3$ 代表 $Super-98$）和该加油站在坐标轴上的位置。加油站的位置不一定按照从左到右的顺序排列。 最后一行包含 $m$ 个整数 $f_i$ $(-10^9 \le f_i < e)$，表示起始位置。起始位置的顺序不一定按照从左到右的顺序排列。 坐标轴上的任何一点都不包含多个加油站。有可能某些点 $f_i$ 或点 $e$ 与加油站重合。

输出恰好 $m$ 行。第 $i$ 行应包含两个整数——如果从点 $f_i$ 开始，$Regular-92$ 和 $Premium-95$ 类型的最小汽油量。首先需要最小化第一个值。如果有多种方式可以实现最小化，则还需要最小化第二个值。 如果从点 $f_i$ 无法到达 Johanna，第 $i$ 行应该写成“$-1 -1$”（不带引号）。