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$.
