Hay Expenses

Every day, Farmer John feeds his cows a lavish meal of premium gourmet hay, and he records the number of bales he used on the next line of his expense notebook.

When tax time comes, FJ realizes that he forgot to record the dates of the feedings. To figure out which feedings belong to which month's expenses, he needs to compute several sums of hay fed over consecutive days.

FJ has a dataset covering $N$ days, numbered $1$ through $N$ ($4 \le N \le 500$). Day $i$ has a hay bale count $H_i$ ($1 \le H_i \le 1{,}000$). There are also $Q$ queries ($1 \le Q \le 500$). Each query is a pair of integers $S_j$ and $E_j$ ($1 \le S_j \le E_j \le N$) giving the start and end indices of a range of days. For each query, output the sum of the hay bale counts for days $S_j$ through $E_j$ (inclusive).

• Line 1: Two space-separated integers $N$ and $Q$.
• Lines 2 to $N+1$: Line $i+1$ contains a single hay bale count $H_i$ for day $i$.
• Lines $N+2$ to $N+Q+1$: Line $j+N+1$ describes query $j$ as a pair of integers $S_j$ and $E_j$.

• Lines 1 to $Q$: Line $j$ contains a single integer, the sum of the hay bale counts for days $S_j$ through $E_j$.

For each query $S_j \dots E_j$, add up the hay bale counts from day $S_j$ to day $E_j$. Precomputing a prefix-sum array lets you answer each query in constant time.