CF581E.Kojiro and Furrari

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.

司机小次郎为购买自己钟爱的汽车品牌“法拉瑞”（Furrari）整整存了10年钱。终于，小次郎的梦想实现了！现在，他想立刻开车去见女友约翰娜，向她炫耀自己的新车。

小次郎要去见女友，因此他将沿一条数轴行进。为简化问题，我们假设小次郎初始位于数轴上的点 $f$，而约翰娜位于点 $e$。数轴上某些位置设有加油站。每个加油站仅提供一种燃油：92号普通汽油（Regular-92）、95号优质汽油（Premium-95）或98号超级汽油（Super-98）。因此，每个加油站由一对整数 $t_i$ 和 $x_i$ 表征——分别表示燃油类型编号及其在数轴上的位置。

每升燃油恰好可驱动汽车行驶 1 公里（该值与燃油类型无关）。三种燃油仅在品质上存在差异，根据研究，品质会影响车辆发动机的使用寿命。一辆法拉瑞汽车的油箱容量恰好为 $s$ 升（与所加燃油类型无关）。出发时（即从小次郎所在点 $f$ 出发的时刻），油箱已完全加满 98 号超级汽油。在每个加油站，小次郎可任意添加任意数量的燃油（但只能是该站所提供的单一类型），当然，在任何时刻，油箱中的燃油总量均不得超过 $s$ 升。注意：油箱中可同时存有不同类型的燃油。汽车既可向左行驶，也可向右行驶。

为延长发动机寿命，小次郎首要目标是最小化所使用的 92 号普通汽油的总量；若存在多种从 $f$ 到 $e$ 的行驶方案，其使用的 92 号普通汽油量均达到最小值，则需在这些方案中进一步最小化所使用的 95 号优质汽油的总量。

请编写一个程序，对 $m$ 个可能的起点位置 $f_i$，分别求出满足上述双重优化目标（先最小化 Regular-92 用量，再最小化 Premium-95 用量）的最优解。

The first line of the input contains four positive integers e, s, n, m (1 ≤ e, s ≤ 109, 1 ≤ n, m ≤ 2·105) — 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,  - 109 ≤ x__i ≤ 109), 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 ( - 109 ≤ f__i < 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.

输入的第一行包含四个正整数 $e$、$s$、$n$、$m$（$1 ≤ e, s ≤ 10^9$，$1 ≤ n, m ≤ 2·10^5$）——分别表示约翰娜当前所在位置的坐标、法拉瑞（Furrari）油箱的容量、加油站的数量以及起始点的数量。

接下来的 $n$ 行每行包含两个整数 $t_i$、$x_i$（$1 ≤ t_i ≤ 3$，$-10^9 ≤ x_i ≤ 10^9$），表示第 $i$ 个加油站的类型（1 表示 92 号普通汽油，2 表示 95 号优质汽油，3 表示 98 号超级汽油）以及该加油站位于坐标轴上的位置。加油站的位置不一定按从左到右的顺序给出。

最后一行包含 $m$ 个整数 $f_i$（$-10^9 ≤ f_i < e$）。起始点的位置也不一定按从左到右的顺序给出。

坐标轴上任意一点至多只存在一个加油站。有可能某些起始点 $f_i$ 或终点 $e$ 的位置恰好与某个加油站重合。

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).

恰好输出 m 行。其中第 i 行应包含两个整数——若 Kojiro 从点 f__i 出发，到达 Johanna 所需的 Regular-92 型汽油与 Premium-95 型汽油的最小用量。首先需最小化第一个数值；若存在多种方案使第一个数值达到最小，则还需进一步最小化第二个数值。

若无法从点 f__i 到达 Johanna，则第 i 行应为 "-1 -1"（不带引号的两个负一）。