Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ và ~q~ truy vấn, mỗi truy vấn gồm hai số ~l, r~.

Với mỗi truy vấn, hãy tính tổng các phần tử có vị trí từ ~l~ đến ~r~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, q \ (1\le n, q\le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n \ (|a_i| \le 10^5, 1\le i\le n)~.
• ~q~ dòng sau, mỗi dòng chứa hai số nguyên ~l_i, r_i \ (1\le l_i \le r_i \le n, 1\le i\le q)~.

Output

Kết quả gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~ ~(1\le i\le q)~.

Ví dụ

Input

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

Output

-1
-3
3