Cho số nguyên dương ~n~ và dãy số nguyên ~a_1, a_2, \dots, a_n~. Có ~q~ câu hỏi, mỗi câu hỏi được cho bởi hai số nguyên ~x_1~, ~x_2~ (~1 \leq x_1 \leq x_2 \leq n~), với mỗi câu hỏi hãy cho biết tổng các số từ vị trí ~x_1~ đến vị trí ~x_2~ trong dãy ~a_1, a_2, \dots, a_n~ là bao nhiêu?

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n~, ~q~.
• Dòng thứ hai ghi lần lượt các số ~a_1, a_2, \dots, a_n~.
• ~q~ dòng tiếp theo, mỗi dòng ghi một cặp số nguyên ~x_1, x_2~.

Giới hạn:

• ~1 \leq n, q \leq 10^5~
• ~|a_i| \leq 10^9~

Output

Ghi trên ~q~ dòng, mỗi dòng là tổng các số từ ~x_1~ đến ~x_2~ trong dãy ~a_1, a_2, \dots, a_n~ tương ứng với thứ tự trong input.

Sample Test

Input

4 2
1 4 2 8
1 3
1 4

Output

7
15