Cho một dãy số nguyên a có n phần tử, yêu cầu hãy tính tổng của các phần tử trong một đoạn con bất kì của dãy a đó.

Input:

• Dòng thứ 1: gồm 2 số n và m, n là số phần tử dãy a và m là số đoạn con cần tính (1 <= n <= 10⁶, 1 <= m <= 10³)
• Dòng thứ 2: gồm n phần tử của dãy a (|a[i]| <= 10⁸).
• m dòng tiếp theo gồm 2 số a,b là 2 mút của đoạn con cần tính tổng (1<=a<=b<=n).

Các số liệu ghi cách nhau ít nhất 1 dấu cách.

Output:

Gồm m dòng, mỗi dòng là tổng của từng đoạn con tương ứng.

Ví dụ:

Input:
4 2
1 2 3 4
2 3
1 4
Output:
5
10