남훈 : 자, 여기 $n$개의 정수로 이루어진 수열이 있어. 이를 $a_1, a_2, ... , a_n$이라 하자. 여기서 특정 구간 $[l, r]$의 합을 구할 수 있을까?

진수 : 뭐야 쉽잖아. 그냥 반복문으로 순회하면 $O(n)$에 풀 수 있어.

남훈 : 음.. 그럼 만약에 $n$이 최대 $100,000$까지 될 수 있고, 그걸 $1$초 내로 $100$번이나 구해야 한다면?

진수 : 그 정도 연산량도 크게 문제 없을 것 같은데? 요즘 컴퓨터는 초 당 억단위 연산을 수행할 수 있어.

남훈 : 그럼 $10,000$번. 아니 $100,000$번 구해야 한다면?

진수 : 그렇게 많이..?

첫째 줄에 수열의 길이를 나타내는 정수 $n$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(1 ≤ n, Q ≤ 100,000)$

둘째 줄에 $a_1, a_2, ... , a_n$이 공백으로 구분되어 주어진다.$(1 ≤ a_i ≤ 1,000)$

셋째 줄부터 $Q$개의 줄에 걸쳐 $l, r$이 공백으로 구분되어 주어진다. $(1 ≤ l ≤ r ≤ n)$