우주 탐사선

우주 탐사선이 제어를 벗어났다. 탐사선은 초 단위로 주어진 두 시각 $t_1$과 $t_2$ 사이의 어떤 시각 $t$에 측정 순서를 시작하지만, 그 시각이 언제인지는 알 수 없다. 구간 $[t_1, t_2]$ 안의 시작 시각 $t$는 모두 같은 확률로 나온다.

측정 순서는 미리 입력되어 있어 바꿀 수 없다. 순서는 $n$번의 연속된 측정으로 이루어지고, 각 측정의 시간차 $m_1, m_2, \dots, m_n$은 고정되어 있다. 순서가 시각 $t$에 시작하면 첫 번째 측정은 시각 $t + m_1$에, 두 번째 측정은 시각 $t + m_2$에, 마지막 측정은 시각 $t + m_n$에 이루어진다. 측정은 순간에 끝나므로 측정에 걸리는 시간은 $0$초로 본다.

탐사선은 우주에서 회전하고 있고 자세를 제어할 수 없다. 회전 때문에 측정 장비가 태양을 향하는 시간 구간이 생긴다. 장비가 태양을 향하는 동안 측정하면 센서가 파괴되고 탐사선 전체를 잃는다. 궤도와 회전은 이미 알고 있으므로, 측정을 하면 안 되는 $k$개의 시간 구간 $[b_1, e_1], [b_2, e_2], \dots, [b_k, e_k]$도 알고 있다.

모든 측정을 무사히 마치고 탐사선이 태양 복사에 파괴되지 않을 확률을 구하시오.

주어지는 시각과 구간 길이는 모두 정수이다. 측정 순서의 시작 시각만 알 수 없고, $[t_1, t_2]$ 안의 어떤 실수든 될 수 있다.

첫째 줄에 정수 $n$, $k$, $t_1$, $t_2$가 주어진다. $n$은 측정 횟수, $k$는 측정을 하면 안 되는 시간 구간의 개수이고, $t_1$과 $t_2$는 측정 순서가 시작될 수 있는 시각의 범위이다.

둘째 줄에 측정 순서가 시작된 뒤 각 측정이 이루어지는 시간차 $m_1, m_2, \dots, m_n$이 정수로 주어진다. 수열 $m_i$는 순증가한다.

다음 $k$개의 줄에는 측정을 하면 안 되는 구간 $[b_j, e_j]$를 나타내는 두 정수 $b_j$와 $e_j$가 주어진다. $b_j < e_j$이고 구간끼리 겹치지 않는다. 즉 $j > 1$인 모든 $j$에 대해 $e_{j-1} < b_j$이다.

• $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}$
• $m_1, \dots, m_n$과 $b_1, e_1, \dots, b_k, e_k$는 모두 $0$ 이상 $10^{16}$ 미만의 정수이다

한 줄에 있는 값은 공백 하나로 구분된다.

탐사선이 살아남을 확률, 즉 어떤 측정도 금지된 구간 안에서 이루어지지 않을 확률을 출력한다.

입력으로 주어지는 값이 모두 정수이므로 이 확률은 유리수이다. 빗금 앞뒤에 공백 없이 기약분수 p/q 꼴로 출력한다. 여기서 $q > 0$이고 $\gcd(p, q) = 1$이다. 확률이 $0$이면 0/1을, $1$이면 1/1을 출력한다.