Cho dãy số nguyên ~ a_i ~ gồm n phần tử.

Cho m yêu cầu có dạng x y , với mỗi yêu cầu, in ra tổng các số của dãy ~ a_i ~ trong đoạn từ x đến y .

Input

• Dòng đầu tiên chứa hai số nguyên dương n và m (~ 1 \le n , m \le 10^5 ~).

• Dòng thứ hai chứa n số nguyên là các phần tử của dãy ~ a_i ~.(~ |a_i| \le 10^9 ~).

• m dòng tiếp theo, mỗi dòng chứa hai số nguyên X và Y thể hiện một yêu cầu (~ 1 \le x \le y \le n ~).

Output

Với mỗi yêu cầu, in ra tổng các số trong đoạn từ x đến y.

Sample

Input #1

3 2
-1 -1 1
2 3
1 1

Output #1

0
-1

Input #2

2 3
-6 -5
1 1
1 2
2 2

Output #2

-6
-11
-5

Problem source: apok