Problem K
Space Probe

Photo by NASA Goddard Space Flight Center

The space probe is out of control! It’s going to start its measurement sequence sometime between two given times $t_1$ and $t_2$ (measured in seconds), but we don’t know when. We do know that all possible start times $t \in [t_1, t_2]$ are equally probable.

The measurement sequence is pre-programmed and cannot be changed. It consists of $n$ successive measurements which have timings $m_1, m_2, \ldots , m_ n$ that are fixed. If $t$ is the time that the probe starts the measurement sequence, the first measurement occurs at time $t+m_1$, the second at time $t+m_2$, and so on. The last measurement occurs at time $t+m_ n$.

The measurements are instantaneous events — each happens in a very short time, so we consider the duration of any measurement to be $0$ seconds.

The probe is rotating in space and cannot be controlled. Due to its rotation, there are intervals of time when measurement devices are pointed at the Sun. If the probe were to use a measurement device while the device is pointed at the Sun, the device’s sensors would be destroyed and the whole probe would be lost. We do know the trajectory and the rotation of the probe and therefore there is a set of $k$ time intervals $[b_1, e_1], [b_2, e_2], \ldots , [b_ k, e_ k]$ during any of which no measurement may be made.

Find the probability that the probe makes all measurements successfully and is not lost due to solar radiation damage!

Note that in this problem, all known times and time interval lengths are expressed as integers. However, the time of the start of the measurement sequence is unknown and we suppose that it may be expressed as any real number in the interval $[t_1, t_2]$.

Input

The first input line contains four integers $n$, $k$, $t_1$, and $t_2$. The value $n$ represents the number of measurements, $k$ represents the number of time intervals in which no measurement may be made, and $t_1$ and $t_2$ represent the time limits in which the measurement sequence can begin. The second input line contains $n$ integers representing the sequence $m_1, m_2, \ldots , m_ n$ of pre-programmed time moments in which measurements are made after the measurement sequence has begun. The sequence $m_ i$ is strictly increasing. Finally, there are $k$ input lines which each have two integers $b_ j$ and $e_ j$ describing one time interval $[b_ j, e_ j]$ in which no measurement may be made. It’s guaranteed that $b_ j < e_ j$, and the intervals do not overlap, i.e., $e_{j-1} < b_ j$ for all $j > 1$.

We know that $1 \le n \leq 10\, 000$, $1 \le k \leq 10\, 000$, $n \cdot k \le 10^{7}$, and $0 \leq t_1 < t_2 \leq 10^{16}$. All values $m_1, \ldots , m_ n$ and $b_1, e_1, \ldots , b_ k, e_ k$ are non-negative and less than $10^{16}$. All values are separated by single spaces.

Output

Output the probability of the probe’s survival, that is, the probability that no measurement will be made during any of the intervals in which the Sun could damage the sensors. Your answer must be within an absolute or relative error of $10^{-6}$ of the correct answer.

2 2 10 20
1 5
12 14
15 18

0.4000000000

6 3 100 200
0 10 20 30 40 50
140 150
170 171
210 300

0.0900000000