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$”(不带引号)。

题目描述

Motorist Kojiro spent $ 10 $ years saving up for his favorite car brand, Furrari. Finally Kojiro's dream came true! Kojiro now wants to get to his girlfriend Johanna to show off his car to her. Kojiro wants to get to his girlfriend, so he will go to her along a coordinate line. For simplicity, we can assume that Kojiro is at the point $ f $ of a coordinate line, and Johanna is at point $ e $ . Some points of the coordinate line have gas stations. Every gas station fills with only one type of fuel: Regular-92, Premium-95 or Super-98. Thus, each gas station is characterized by a pair of integers $ t_{i} $ and $ x_{i} $ — the number of the gas type and its position. One liter of fuel is enough to drive for exactly $ 1 $ km (this value does not depend on the type of fuel). Fuels of three types differ only in quality, according to the research, that affects the lifetime of the vehicle motor. A Furrari tank holds exactly $ s $ liters of fuel (regardless of the type of fuel). At the moment of departure from point $ f $ Kojiro's tank is completely filled with fuel Super-98. At each gas station Kojiro can fill the tank with any amount of fuel, but of course, at no point in time, the amount of fuel in the tank can be more than $ s $ liters. Note that the tank can simultaneously have different types of fuel. The car can moves both left and right. To extend the lifetime of the engine Kojiro seeks primarily to minimize the amount of fuel of type Regular-92. If there are several strategies to go from $ f $ to $ e $ , using the minimum amount of fuel of type Regular-92, it is necessary to travel so as to minimize the amount of used fuel of type Premium-95. Write a program that can for the $ m $ possible positions of the start $ f_{i} $ minimize firstly, the amount of used fuel of type Regular-92 and secondly, the amount of used fuel of type Premium-95.

输入输出格式

输入格式


The first line of the input contains four positive integers $ e,s,n,m $ ( $ 1<=e,s<=10^{9},1<=n,m<=2·10^{5} $ ) — the coordinate of the point where Johanna is, the capacity of a Furrari tank, the number of gas stations and the number of starting points. Next $ n $ lines contain two integers each $ t_{i},x_{i} $ ( $ 1<=t_{i}<=3,-10^{9}<=x_{i}<=10^{9} $ ), representing the type of the $ i $ -th gas station ( $ 1 $ represents Regular-92, $ 2 $ — Premium-95 and $ 3 $ — Super-98) and the position on a coordinate line of the $ i $ -th gas station. Gas stations don't necessarily follow in order from left to right. The last line contains $ m $ integers $ f_{i} $ ( $ -10^{9}<=f_{i}&lt;e $ ). Start positions don't necessarily follow in order from left to right. No point of the coordinate line contains more than one gas station. It is possible that some of points $ f_{i} $ or point $ e $ coincide with a gas station.

输出格式


Print exactly $ m $ lines. The $ i $ -th of them should contain two integers — the minimum amount of gas of type Regular-92 and type Premium-95, if Kojiro starts at point $ f_{i} $ . First you need to minimize the first value. If there are multiple ways to do it, you need to also minimize the second value. If there is no way to get to Johanna from point $ f_{i} $ , the $ i $ -th line should look like that "-1 -1" (two numbers minus one without the quotes).

输入输出样例

输入样例 #1

8 4 1 1
2 4
0

输出样例 #1

0 4

输入样例 #2

9 3 2 3
2 3
1 6
-1 0 1

输出样例 #2

-1 -1
3 3
3 2

输入样例 #3

20 9 2 4
1 5
2 10
-1 0 1 2

输出样例 #3

-1 -1
-1 -1
-1 -1
-1 -1