Range sum

You are given an array of $n$ integers and $q$ queries. For every query find the sum $a_l + a_{l+1} + \ldots + a_r$.

The first line contains $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$). The second line contains $n$ integers ($|a_i| \le 10^9$). Each of the next $q$ lines contains a query: two integers $l$ and $r$ ($1 \le l \le r \le n$).

For every query print one number on a separate line — the sum.

Summing with a loop in every query is $O(nq)$ — $4 \cdot 10^{10}$ operations. Compute the prefix sums $p_i = a_1 + \ldots + a_i$ ($p_0 = 0$) once; then every answer is $p_r - p_{l-1}$ in $O(1)$.

The sum reaches $2 \cdot 10^{14}$ — a 64-bit type is needed.

Source: CSES, problem 1646.