Firefly is given an array $a$ of length $n$. Let $c_i$ denote the $i$'th cyclic shift$^{\text{∗}}$ of $a$. She creates a new array $b$ such that $b = c_1 + c_2 + \dots + c_n$ where $+$ represents concatenation$^{\text{†}}$.

Then, she asks you $q$ queries. For each query, output the sum of all elements in the subarray of $b$ that starts from the $l$-th element and ends at the $r$-th element, inclusive of both ends.

Input

The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ ($1 \leq n, q \leq 2 \cdot 10^5$) — the length of the array and the number of queries.

The following line contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \leq a_i \leq 10^6$).

The following $q$ lines contain two integers $l$ and $r$ ($1 \leq l \leq r \leq n^2$) — the left and right bounds of the query.

Note that the large inputs may require the use of 64-bit integers.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ and the sum of $q$ does not exceed $2 \cdot 10^5$.

Output

For each query, output the answer on a new line.

见题面 Input 部分

见题面 Output 部分

For the first test case, $b = [1, 2, 3, 2, 3, 1, 3, 1, 2]$.