← 返回题目列表

Codeforces · 581/E

E. 小次郎和芙拉里

中文机器翻译题面 查看原题

驾车者 Kojiro 花了 10 年的时间为他最喜欢的汽车品牌 Furrari 存钱。小次郎的梦想终于实现了!小次郎现在想要去找他的女朋友约翰娜,向她展示他的汽车。

小次郎想要去找他的女朋友,所以他会沿着坐标线去找她。为了简单起见,我们可以假设小次郎位于坐标线的 f 点,而约翰娜位于 e 点。坐标线上的一些点有加油站。每个加油站只加注一种类型的燃油:Regular-92、Premium-95 或 Super-98。因此,每个加油站都由一对整数 ti 和 xi 来表征——气体类型的编号及其位置。

一升燃油足以行驶 1 公里(该值与燃油类型无关)。根据研究,三种类型的燃料仅在质量上有所不同,这会影响车辆发动机的使用寿命。 Furrari 油箱可容纳 s 升燃料(无论燃料类型如何)。在离开 f 点时,小次郎的油箱已完全加满 Super-98 燃料。在每个加油站,小次郎都可以给油箱加满任意数量的燃油,但当然,在任何时候,油箱中的燃油量都可能超过 s 升。请注意,油箱可以同时装有不同类型的燃料。汽车可以左右移动。

为了延长发动机的使用寿命,Kojiro 主要寻求最大限度地减少 Regular-92 型燃油量。如果有多种策略从 f 到 e,使用最少量的 Regular-92 型燃油,则需要以最小化使用的 Premium-95 型燃油量的方式行驶。

编写一个程序,可以针对起始 fi 的 m 个可能位置,首先最小化 Regular-92 类型的已用燃料量,其次最小化 Premium-95 类型的已用燃料量。

输入

输入的第一行包含四个正整数 e, s, n, m (1 ≤ e, s ≤ 109, 1 ≤ n, m ≤ 2·105) — Johanna 所在点的坐标、Furrari 油箱的容量、加油站数量和起点数量。

接下来的n行包含两个整数ti,xi(1≤ti≤3,-109≤xi≤109),代表第i个加油站的类型(1代表Regular-92,2代表Premium-95,3代表Super-98)以及第i个加油站在坐标线上的位置。加油站不一定按照从左到右的顺序排列。

最后一行包含 m 个整数 fi ( - 109 ≤ fi < e)。起始位置不一定按从左到右的顺序排列。

坐标线上没有一点包含多个加油站。有可能某些点 fi 或点 e 与加油站重合。

输出

精确打印 m 行。其中第 i 个应该包含两个整数 - 如果 Kojiro 从点 fi 开始,Regular-92 类型和 Premium-95 类型的最小气体量。首先,您需要最小化第一个值。如果有多种方法可以做到这一点,您还需要最小化第二个值。

如果无法从 fi 点到达 Johanna,则第 i 行应该类似于“-1 -1”(两个数字减一,不带引号)。

示例

输入 #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