cs_207 Tính tổng các đoạn từ L đến R

Cho dãy a gồm n số nguyên và k yêu cầu, trong đó mỗi yêu cầu gồm 2 số L và R. Nhiệm vụ của bạn là tính tổng các đoạn từ L đến R trong dãy.

Đầu vào

Dòng đầu tiên chứa số nguyên n và k Dòng tiếp theo chứa n số nguyên a_i (10^-9<=a[i]<=10^9) k dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R

Đầu ra

Gồm k giá trị trên 1 dòng, tương ứng với yêu cầu. Ví dụ

INPUT

10 3

9 2 4 6 -3 8 -20 31 19 10

1 1

9 10

3 5

OUTPUT

9 29 7