Cho mảng \(A\) gồm \(n\) số nguyên. Định nghĩa:

\(f(l,r) = 1 \times A_l + 2 \times A_{l+1} + ... (r-l+1) \times A_r\)

Cho \(q\) truy vấn dạng \((l,r)\), tìm \(f(l,r)\).

Input

• Dòng thứ nhất gồm hai số nguyên \(n,q\).
• Dòng tiếp theo gồm \(n\) số nguyên \(A_i\).
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(l,r\), một truy vấn.

Output

• Với mỗi truy vấn, in ra một số nguyên là đáp án

Điều kiện

• \(1 \le n, q \le 10^{5}\)
• \(1 \le l, r \le n\)
• \(|A_i| \le 10^6\)

Sample Input 1

3 2
-1 3 2
1 3
2 3

Sample Output 1

11
7