You are given an array $A$ of length $N$. You are asked $Q$ queries. Each query is of the form $L,R$, and the answer is the sum of $A[i]$ for all $i$ such that $0 \leq i \leq L$ and $A[ i ] > A[ R ]$.

Print an array $B$ of length $Q$ such that $B[i]$ is the answer to the $i^{th}$ query.

Input format

• The first line of input contains a single integer $T$, which denotes the number of test cases.
• The first line of each test case contains two integers $N$ and $Q$, denoting the length of the array $A$ and the number of queries, respectively.
• The second line of each test case contains $N$ integers, denoting the array $A$.
• The following $Q$ lines of each test case contains two integers $L,R$ denoting each query.

Output format

For each test case, print an array $B$ of length $Q$ separated by space such that $B[i]$ is the answer to the $i^{th}$ query in a new line.

Constraints

$1 \leq T \leq 10 \\ 1 \leq N, Q \leq 10^5 \\ 1 \leq A[i] \leq 10^5 \\ 0 \leq L, R \lt N$