Cho số nguyên dương ~n~ và dãy số nguyên ~a_1,a_2,…,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≤x_1≤x_2≤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,…,a_n~ là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên dương ~n,q~ ~(1≤n,q≤10^5)~.
• Dòng thứ hai ghi lần lượt các số ~a_1,a_2,…,a_n~ ~(0≤|a_i |≤10^9)~
• ~q~ dòng tiếp theo mỗi dòng ghi một cặp số nguyên ~x_1,x_2~ ~(1≤x_1≤x_2≤n)~.

Kết quả:

• 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,…,a_n~ tương ứng với thứ tự trong input

Ví dụ:

Input:

4 2
1 4 2 8
1 3
1 4 

Output:

7
15