Range sum queries

You are given $N$ numbers. Write a program that computes the sum of the $i$-th number through the $j$-th number.

The first line contains the count of numbers $N$ and the number of sums to compute $M$. The second line contains the $N$ numbers in order. Each number is a natural number no greater than 1,000. Each of the next $M$ lines contains the start position $i$ and the end position $j$ of one range.

Print the sum of each range on its own line, in the order the ranges are given, for a total of $M$ lines. The sum from the $i$-th number to the $j$-th number includes both endpoints.

• $1 \le N \le 100{,}000$
• $1 \le M \le 100{,}000$
• $1 \le i \le j \le N$