I. Михаил и билборды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Индустриализация добралась до самых отдалённых уголков страны, и наружная реклама уже вовсю показывается в Байтландии.

Реклама на билбордах показывается по определённым правилам:

  • каждый рекламодатель назначает ставку, которую он готов заплатить за своё объявление;
  • в момент предполагаемого показа определяется список рекламных объявлений, готовых показаться на билборде, который находится в определённой точке;
  • RTB-система (Real-time bidding) проводит аукцион второй цены между всеми объявлениями.

Аукцион второй цены проходит по следующей схеме:

  • отсеиваются объявления, которые не готовы заплатить не менее минимальной ставки $$$MinCost$$$;
  • рекламные объявления сортируются по убыванию ставок;
  • первое объявление назначается победителем;
  • со счёта рекламодателя списывается ставка второго объявления или $$$MinCost$$$, если объявление в аукционе одно.
  • если есть несколько объявлений с максимальной ставкой $$$Cost$$$, то победитель из них выбирается случайно; в таком случае с рекламодателя списывается $$$Cost$$$.

Одной из новинок в индустрии рекламы является геотаргетинг — возможность задать окружность на карте, ограничивающую множество щитов, на которых необходимо производить рекламные показы конкретного объявления. Волевым решением Байтландия была выбрана в качестве испытательного полигона для новой функциональности. Перед аналитиком Михаилом стоит задача: определить места в городе, в которых рекламодатели готовы заплатить наибольшее количество денег. Для этого Михаил прикрепил огромный билборд на свой автомобиль и решил проехать по прямой улице из точки $$$(X_{start}, Y_{start})$$$. Автомобиль Михаила может ехать только с постоянной скоростью. В некоторые моменты времени аналитик останавливается и проверяет, какая реклама показывается на его билборде.

Помогите аналитику Михаилу определить лучшие места для расположения билбордов.

Входные данные

Первая строка входных данных содержит 4 целых числа $$$-10^9 \leq X_{start}, Y_{start}, dx, dy \leq 10^9$$$ — стартовую точку и вектор движения, который автомобиль проезжает за единицу времени. Гарантируется, что либо $$$dx$$$, либо $$$dy$$$ равен нулю, но при этом они не равны нулю одновременно.

Вторая строка содержит количество остановок $$$1 \leq N \leq 3\cdot 10^5$$$. Третья строка содержит $$$N$$$ возрастающих целых чисел $$$0 \leq t_i \leq 10^9$$$. Четвёртая строка содержит 2 числа: количество объявлений $$$1 \leq M \leq 10^5$$$ и минимальную ставку $$$1 \leq MinCost \leq 10^9$$$.

Далее следует $$$M$$$ окружностей, описывающих настройки соответствующих объявлений. Каждая окружность описывается 4 целыми числами: $$$-10^9 \leq X, Y \leq 10^9$$$ — центр окружности, радиус $$$1 \leq R \leq 10^9$$$ и ставка $$$1 \leq Cost \leq 10^9$$$.

Выходные данные

Выведите $$$N$$$ чисел — стоимость победившего объявления в моменты времени $$$t_1, \ldots, t_N$$$.

Примеры
Входные данные
0 0 0 1
10
0 1 2 3 4 5 6 7 8 9
4 50
0 2 1 100
0 4 1 200
0 6 1 300
0 7 1 250
Выходные данные
50 50 50 100 50 200 250 250 50 50
Входные данные
-3 -1 3 0
3
1 3 20
3 100
6 -1 1 400
8 -1 9 300
0 -3 3 200
Выходные данные
200 300 100