16번 - 폭탄의 악마

피돌이는 길이가 $N$인 수열 $\mathbf{A}$로 표현되는 피갤에 여러 개의 폭탄을 던질 계획을 세웠다. 피돌이의 이 엄청난 계획을 알게 된 피붕이는 폭탄들이 모두 터진 이후 피갤의 피해 정도를 예측하고자 한다. 피돌이의 계획은 다음과 같은 행동을 $M$번 수행하는 것이다. \begin{itemize} \item $i \ j$: $A_i, A_{i+1},\ \dots, A_j$에 폭탄을 던진다. \end{itemize} 이때, 폭탄을 맞은 각 원소는 폭발에 휘말려 즉시 자신의 서로 다른 소인수들 중 하나의 값으로 변하게 된다. 또한, 각 소인수로 변할 확률은 균일하다. 피붕이를 대신해, 계획된 모든 폭발이 일어난 후 수열의 모든 원소의 합의 기댓값을 구해보자! \begin{center} \begin{tabular}{|c|c|l|} \hline 번호 & 배점 & 제한 \\ \hline 1 & 4 & $M = 0$ \\ \hline 2 & 20 & 각 계획은 서로 교차하지 않는다. \\ \hline 3 & 76 & 추가적인 제약 조건이 없다. \\ \hline \end{tabular} \end{center}

첫째 줄에 수열의 길이 $N$과 계획의 수 $M$이 주어진다. ($1 \le N \le 200\,000, 0 \le M \le 200\,000$) 둘째 줄에 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($2 \le A_i \le 500\,000$, $A_i$는 정수) 셋째 줄부터 $M$개의 줄에 걸쳐 피돌이의 계획 $i, j$가 주어진다. ($1 \le i \le j \le N$)

첫째 줄에 모든 폭발이 적용된 이후 수열의 모든 원소의 합의 기댓값을 출력한다. 출력한 값과 정답의 상대/절대 오차가 $10^{-9}$이하라면 정답으로 인정된다.

값이 12인 원소에 폭발이 일어난다면, $12$의 서로 다른 소인수는 $2$와 $3$이므로, 이 원소는 폭발 이후 $1/2$의 확률로 $2$로, $1/2$의 확률로 $3$으로 변한다.