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.

$$$^{\text{∗}}$$$The $$$x$$$-th ($$$1 \leq x \leq n$$$) cyclic shift of the array $$$a$$$ is $$$a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}$$$. Note that the $$$1$$$-st shift is the initial $$$a$$$.

$$$^{\text{†}}$$$The concatenation of two arrays $$$p$$$ and $$$q$$$ of length $$$n$$$ (in other words, $$$p + q$$$) is $$$p_1, p_2, ..., p_n, q_1, q_2, ..., q_n$$$.

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.

Note

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

Firefly's Queries

Examples