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\)