На протяжении 10 лет автолюбитель Кодзиро собирал деньги на свою любимую машину марки Furrari. Наконец заветная мечта Кодзиро сбылась! Теперь Кодзиро хочет доехать до своей подруги Йоханны, чтобы похвастаться перед ней своей машиной.
Кодзиро хочет доехать до подруги, поэтому он будет ехать к ней по числовой прямой. Для простоты можно считать, что Кодзиро находится в точке с абсциссой f числовой прямой, а Йоханна — в точке с абсциссой e. В некоторых точках числовой прямой находятся бензозаправки. На каждой бензозаправке заправляют только одним видом топлива: Регуляр-92, Премиум-95 или Супер-98. Таким образом, каждая заправка характеризуется парой целых чисел ti и xi — номером типа бензина и своей позицией.
Одного литра бензина достаточно, чтобы проехать ровно 1 км (эта величина не зависит от типа бензина). Бензины трех видов отличаются лишь качеством, которое по данным исследований влияет на время жизни двигателя автомобиля. Бак Furrari вмещает ровно s литров бензина (независимо от типа бензина). В момент выезда из точки f бак Кодзиро полностью заполнен бензином марки Супер-98. На каждой заправке Кодзиро может заправить бак любым количеством бензина, но, конечно, ни в какой момент времени количество бензина в баке не может стать больше s литров. Обратите внимание, что в баке может одновременно находиться бензин разных типов. Машина может двигаться как влево, так и вправо.
Для продления времени жизни двигателя Кодзиро старается в первую очередь минимизировать количество бензина типа Регуляр-92. Если существует несколько стратегий проехать из f в e, использовав минимальный объем бензина типа Регуляр-92, то надо проехать так, чтобы минимизировать использованный объем бензина Премиум-95.
Напишите программу, которая для m возможных положений старта fi минимизирует объем потраченного бензина типа Регуляр-92 и объем потраченного бензина типа Премиум-95 во вторую очередь.
В первой строке входных данных находятся четыре целых положительных числа e, s, n, m (1 ≤ e, s ≤ 109, 1 ≤ n, m ≤ 2·105) — координата точки, в которой находится Йоханна, размер бака Furrari, количество бензозаправок и количество стартовых точек.
В следующих n строках находится по два целых числа ti, xi (1 ≤ ti ≤ 3, - 109 ≤ xi ≤ 109), обозначающие тип i-й бензозаправки (1 — для Регуляр-92, 2 — для Премиум-95 и 3 — для Супер-98) и положение на координатной прямой i-й заправки. Заправки следуют в произвольном порядке (не обязательно слева направо).
В последней строке находится m целых чисел fi ( - 109 ≤ fi < e). Стартовые позиции следуют в произвольном порядке (не обязательно слева направо).
Ни в какой точке координатной прямой не находится более одной бензозаправки. Допустимо, что некоторые из точек fi или точка e совпадут с заправкой.
Выведите ровно m строк. В i-й из них должно находиться два целых числа — минимальное количество бензина типа Регуляр-92 и типа Премиум-95, если Кодзиро стартует в точке fi. В первую очередь необходимо минимизировать первое значение, при разных способах достичь его надо минимизировать второе значение.
Если доехать до Йоханны из точки fi никак не получится, i-я строка должна иметь вид «-1 -1» (две минус единицы без кавычек).
8 4 1 1
2 4
0
0 4
9 3 2 3
2 3
1 6
-1 0 1
-1 -1
3 3
3 2
20 9 2 4
1 5
2 10
-1 0 1 2
-1 -1
-1 -1
-1 -1
-1 -1
| Codeforces Round 322 (Div. 2) |
|---|
| Закончено |
