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

1
3 4
1 1 5
2 3
1 3
3 3
1 1

5/4