Problem Statement

You are given an integer sequence $(A_1,\dots,A_N)$ of length $N$.

Construct a sequence $B$ of length $\frac{N(N+1)}{2}$ by the following procedure.

• Initially, let $B$ be an empty sequence.
• For $i=1,2,\dots,N$ in this order, append $(A_1,\dots,A_i)$ to the end of $B$.

You are given $Q$ queries of the following form; answer them.

Query: You are given $L$ and $R$. Find $B_L+B_{L+1}+\dots+B_R$.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $-10^8 \leq A_i \leq 10^8$
• For each query, $1\leq L\leq R \leq \frac{N(N+1)}{2}$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Here, $\mathrm{query}_i$ represents the $i$-th query and is given in the following format:

L R

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.