Space Probe

A space probe is out of control. It starts its measurement sequence at some time $t$, measured in seconds, that lies between $t_1$ and $t_2$, and nobody knows exactly when. Every start time $t$ in the interval $[t_1, t_2]$ is equally likely.

The measurement sequence is preprogrammed and cannot be changed. It consists of $n$ successive measurements whose offsets $m_1, m_2, \dots, m_n$ are fixed. If the sequence starts at time $t$, the first measurement happens at time $t + m_1$, the second at time $t + m_2$, and the last one at time $t + m_n$. A measurement is instantaneous, so its duration is $0$ seconds.

The probe rotates in space and cannot be steered. Because of the rotation there are stretches of time during which the measuring devices point at the Sun. A measurement taken while a device points at the Sun destroys its sensors and the whole probe is lost. The trajectory and the rotation are known, so the $k$ time intervals $[b_1, e_1], [b_2, e_2], \dots, [b_k, e_k]$ during which no measurement may be taken are known as well.

Compute the probability that every measurement succeeds and the probe is not lost to solar radiation.

All given times and interval lengths are integers. Only the start time of the sequence is unknown, and it may be any real number in $[t_1, t_2]$.

The first line contains four integers $n$, $k$, $t_1$, $t_2$. Here $n$ is the number of measurements, $k$ is the number of time intervals in which no measurement may be taken, and $t_1$ and $t_2$ bound the window in which the measurement sequence can begin.

The second line contains $n$ integers $m_1, m_2, \dots, m_n$, the offsets at which the measurements happen after the sequence begins. The sequence $m_i$ is strictly increasing.

Each of the following $k$ lines contains two integers $b_j$ and $e_j$ that describe one forbidden interval $[b_j, e_j]$. It is guaranteed that $b_j < e_j$ and that the intervals do not overlap, that is, $e_{j-1} < b_j$ for every $j > 1$.

• $1 \le n \le 10^4$
• $1 \le k \le 10^4$
• $n \times k \le 10^7$
• $0 \le t_1 < t_2 \le 10^{16}$
• all values $m_1, \dots, m_n$ and $b_1, e_1, \dots, b_k, e_k$ are non-negative and smaller than $10^{16}$

Values on one line are separated by single spaces.

Print the probability that the probe survives, that is, the probability that no measurement falls inside any forbidden interval.

Every input value is an integer, so this probability is a rational number. Print it as an irreducible fraction in the form p/q, with no space around the slash, where $q > 0$ and $\gcd(p, q) = 1$. Print a probability of $0$ as 0/1 and a probability of $1$ as 1/1.