Victor and Toys

Accepts: 18
Submissions: 129
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 262144/131072 K (Java/Others)
Problem Description
Victor has $n$ toys, numbered from $1$ to $n$. The beauty of the $i$-th toy is $w_i$. Victor has a sense of math and he generates $m$ intervals, the $i$-th interval is $[l_i,r_i]$. He randomly picks $3$ numbers $i,j,k(1\leq i < j < k \leq m)$, and selects all of the toys whose number are no less than $\max(l_i,l_j,l_k)$ and no larger than $\min(r_i,r_j,r_k)$. Now he wants to know the expected sum of beauty of the selected toys, can you help him?
Input
The first line of the input contains an integer $T$, denoting the number of test cases. In every test case, there are two integers $n$ and $m$ in the first line, denoting the number of the toys and intervals. The second line contains $n$ integers, the $i$-th integer $w_i$ denotes that the beauty of the $i$-th toy. Then there are $m$ lines, the $i$-th line contains two integers $l_i$ and $r_i$. $1\leq T\leq 10$. $1\leq n,m\leq 50000$. $1\leq w_i\leq 5$. $1\leq l_i\leq r_i\leq n$.
Output
Your program should print $T$ lines : the $i$-th of these denotes the answer of the $i$-th case. If the answer is an integer, just print a single interger, otherwise print an irreducible fraction like $p/q$.
Sample Input
1
3 4
1 1 5
2 3
1 3
3 3
1 1
Sample Output
5/4