Cho mảng ~A~ gồm ~n~ số nguyên. Ta định nghĩa:

$$f(l,r) = 1 \times A_l + 2 \times A_{l+1} + \dots + (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~ (~1 \le n, q \le 10^5~).

Dòng tiếp theo gồm ~n~ số nguyên ~A_i~ (~|A_i| \le 10^6~).

~q~ dòng tiếp theo. mỗi dòng gồm hai số nguyên ~l, r~ (~1 \le l, r \le n~) một truy vấn.

Output

Dòng thứ nhất gồm hai số nguyên ~n, q~ (~1 \le n, q \le 10^5~).

Dòng tiếp theo gồm ~n~ số nguyên ~A_i~ (~|A_i| \le 10^6~).

~q~ dòng tiếp theo. mỗi dòng gồm hai số nguyên ~l, r~ (~1 \le l, r \le n~) một truy vấn.

Sample Input 1

5 3
5 8 10 -10 9
4 4
2 5
5 5

Sample Output 1

-10
34
9

Sample Input 2

5 3
3 -5 -1 -4 -9
3 3
2 5
4 5

Sample Output 2

-1
-55
-22