Вася очень любит физику. Освоив основы электродинамики, он решил создать собственную модель гаусс-пушки. Ключевыми элементами пушки являются ускорители, позволяющие снаряду приобрести огромную начальную скорость. Каждый ускоритель содержит две концентрические окружности — основные кольца. Кольца ускорителя соединены некоторым количеством резисторов. Каждый из резисторов представляет собой отрезок, соединяющий два кольца, который лежит на прямой, проходящей через центры колец. Для проверки качества ускорителя необходимо уметь определять, за какое время заряд может дойти от одной точки основного кольца, до другой точки (возможно, другого) основного кольца. Заряд может двигаться по первому основному кольцу, тратя T1 единиц времени на прохождение одного радиана, по второму кольцу — тратя T2 единиц времени на радиан. Кроме того, заряд может проходить через резисторы, тратя T единиц времени на каждый резистор. Как по кольцам, так и по резисторам допускается движение в любом направлении. Разумеется, при переходе через резистор заряд окажется на другом основном кольце.
Конфигурация ускорителя, соответствующая примеру, приведена на картинке ниже.
Зная параметры T1, T2 и T, а также конфигурацию ускорителя (положение резисторов), определите время прохождения заряда между указанными парами точек. Толщиной колец и резисторов можно пренебречь.
В первой строке находятся 3 целых числа — T1, T2 и T (1 ≤ T1, T2, T ≤ 1000). Во второй строке — единственное число N — количество резисторов в ускорителе (1 ≤ N ≤ 200000). В следующей строке находятся N вещественных чисел Ai, содержащих ровно 4 знака после десятичной точки, — углы положения резисторов. Углы заданы в радианах, 0 ≤ Ai < 2π, все числа Ai различны.
В следующей строке задано единственное число M — количество запросов на нахождение времени прохождения заряда (1 ≤ M ≤ 100000). В каждой из M следующих строк находятся 4 числа — C1, X1, C2, X2 — описание начальной и конечной точек движения заряда. Ci равно 1, если точка находится на первом кольце, 2 — если на втором кольце. Xi — угол (в радианах) положения точки на кольце, 0 ≤ Xi < 2π, Xi содержит ровно 4 знака после десятичной точки.
Для каждого из M запросов нужно вывести одно вещественное число на отдельной строке — минимальное время, которое потребуется заряду для перехода между двумя соответствующими точками. Ответ должен быть дан с абсолютной или относительной погрешностью, не превышающей 10 - 6.
В примере имеется 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.
## Входные Данные
В первой строке находятся 3 целых числа — T1, T2 и T (1 ≤ T1, T2, T ≤ 1000). Во второй строке — единственное число N — количество резисторов в ускорителе (1 ≤ N ≤ 200000). В следующей строке находятся N вещественных чисел Ai, содержащих ровно 4 знака после десятичной точки, — углы положения резисторов. Углы заданы в радианах, 0 ≤ Ai < 2π, все числа Ai различны.В следующей строке задано единственное число M — количество запросов на нахождение времени прохождения заряда (1 ≤ M ≤ 100000). В каждой из M следующих строк находятся 4 числа — C1, X1, C2, X2 — описание начальной и конечной точек движения заряда. Ci равно 1, если точка находится на первом кольце, 2 — если на втором кольце. Xi — угол (в радианах) положения точки на кольце, 0 ≤ Xi < 2π, Xi содержит ровно 4 знака после десятичной точки.
## Выходные Данные
Для каждого из M запросов нужно вывести одно вещественное число на отдельной строке — минимальное время, которое потребуется заряду для перехода между двумя соответствующими точками. Ответ должен быть дан с абсолютной или относительной погрешностью, не превышающей 10 - 6.
## Примеры
Входные данные4 1 221.0000 2.000031 0.0000 1 1.50001 1.6000 2 1.60001 1.6000 2 0.6000Выходные данные6.0000000004.0000000004.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.
[samples]
**Definitions**
Let $ T_1, T_2, T \in \mathbb{Z}^+ $ be the time costs per radian on ring 1, ring 2, and per resistor, respectively.
Let $ N \in \mathbb{Z}^+ $ be the number of resistors.
Let $ A = \{a_1, a_2, \dots, a_N\} \subset [0, 2\pi) $ be the set of angular positions (in radians) of the resistors, all distinct.
Let $ M \in \mathbb{Z}^+ $ be the number of queries.
Each query is a tuple $ (c_1, x_1, c_2, x_2) $, where:
- $ c_i \in \{1,2\} $: the ring index of the start/end point,
- $ x_i \in [0, 2\pi) $: the angular position (in radians) of the point on its ring.
**Constraints**
1. $ 1 \leq T_1, T_2, T \leq 1000 $
2. $ 1 \leq N \leq 200000 $
3. $ 1 \leq M \leq 100000 $
4. All $ a_i $ and $ x_i $ have exactly 4 decimal places, $ 0 \leq a_i, x_i < 2\pi $, all $ a_i $ distinct.
**Objective**
For each query $ (c_1, x_1, c_2, x_2) $, compute the minimal time to travel from point $ (c_1, x_1) $ to $ (c_2, x_2) $, where:
- Movement along a ring $ i \in \{1,2\} $ costs $ T_i \cdot d $, where $ d $ is the shortest angular distance (in radians) along the circle:
$$
d(\theta_1, \theta_2) = \min\left( |\theta_1 - \theta_2|, 2\pi - |\theta_1 - \theta_2| \right)
$$
- Movement through a resistor at angle $ a_j $ costs $ T $, and allows transition between rings at the same angular position.
- The path may involve:
- Direct movement along the same ring (if $ c_1 = c_2 $),
- Movement to a resistor on ring $ c_1 $, cross it, then move along ring $ c_2 $ to the target,
- Or multiple resistor crossings (but minimal path will use at most one, due to convexity).
**Minimization**
For each query, compute:
$$
\min \left\{
\begin{array}{l}
T_{c_1} \cdot d(x_1, x_2) \quad \text{(direct on same ring)} \\
\min_{j=1}^{N} \left( T_{c_1} \cdot d(x_1, a_j) + T + T_{c_2} \cdot d(a_j, x_2) \right) \quad \text{(via one resistor)} \\
\end{array}
\right.
$$