401795: GYM100528 L Пушка Гаусса

L. Пушка Гауссаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводstandard inputвыводstandard output

Вася очень любит физику. Освоив основы электродинамики, он решил создать собственную модель гаусс-пушки. Ключевыми элементами пушки являются ускорители, позволяющие снаряду приобрести огромную начальную скорость. Каждый ускоритель содержит две концентрические окружности — основные кольца. Кольца ускорителя соединены некоторым количеством резисторов. Каждый из резисторов представляет собой отрезок, соединяющий два кольца, который лежит на прямой, проходящей через центры колец. Для проверки качества ускорителя необходимо уметь определять, за какое время заряд может дойти от одной точки основного кольца, до другой точки (возможно, другого) основного кольца. Заряд может двигаться по первому основному кольцу, тратя T₁ единиц времени на прохождение одного радиана, по второму кольцу — тратя T₂ единиц времени на радиан. Кроме того, заряд может проходить через резисторы, тратя T единиц времени на каждый резистор. Как по кольцам, так и по резисторам допускается движение в любом направлении. Разумеется, при переходе через резистор заряд окажется на другом основном кольце.

Конфигурация ускорителя, соответствующая примеру, приведена на картинке ниже.

Зная параметры T₁, T₂ и T, а также конфигурацию ускорителя (положение резисторов), определите время прохождения заряда между указанными парами точек. Толщиной колец и резисторов можно пренебречь.

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

В первой строке находятся 3 целых числа — T₁, T₂ и T (1 ≤ T₁, T₂, T ≤ 1000). Во второй строке — единственное число N — количество резисторов в ускорителе (1 ≤ N ≤ 200000). В следующей строке находятся N вещественных чисел A_i, содержащих ровно 4 знака после десятичной точки, — углы положения резисторов. Углы заданы в радианах, 0 ≤ A_i < 2π, все числа A_i различны.

В следующей строке задано единственное число M — количество запросов на нахождение времени прохождения заряда (1 ≤ M ≤ 100000). В каждой из M следующих строк находятся 4 числа — C₁, X₁, C₂, X₂ — описание начальной и конечной точек движения заряда. C_i равно 1, если точка находится на первом кольце, 2 — если на втором кольце. X_i — угол (в радианах) положения точки на кольце, 0 ≤ X_i < 2π, X_i содержит ровно 4 знака после десятичной точки.

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

Для каждого из M запросов нужно вывести одно вещественное число на отдельной строке — минимальное время, которое потребуется заряду для перехода между двумя соответствующими точками. Ответ должен быть дан с абсолютной или относительной погрешностью, не превышающей 10^- 6.

ПримерыВходные данные

4 1 2
2
1.0000 2.0000
3
1 0.0000 1 1.5000
1 1.6000 2 1.6000
1 1.6000 2 0.6000

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

6.000000000
4.000000000
4.800000000

Примечание

В примере имеется 2 резистора, в позиции 1 радиан и 2 радиана.

В первом запросе нужно пройти между двумя точками первого кольца. Расстояние между точками — 1.5 радиан. Поэтому потребуется время 4·1.5 = 6.

Во втором запросе нужно из точки первого кольца перейти в точку второго кольца. Быстрее всего сделать это, пройдя через второй резистор. Для этого потребуется 4·(2 - 1.6) + 2 + 1·(2 - 1.6) = 4 единицы времени.

В последнем запросе, в отличие от предыдущего, выгоднее двигаться через первый резистор. Искомое время равно 4·(1.6 - 1) + 2 + (1 - 0.6) = 4.8.