구간 합 구하기

수 $N$개가 주어진다. 이 중 $i$번째 수부터 $j$번째 수까지 더한 값을 구하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 $N$과 합을 구해야 하는 횟수 $M$이 주어진다. 둘째 줄에 $N$개의 수가 순서대로 주어진다. 각 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 $M$개의 줄에 걸쳐 합을 구할 구간의 시작 위치 $i$와 끝 위치 $j$가 주어진다.

$M$개의 줄에 걸쳐 각 구간의 합을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다. $i$번째 수부터 $j$번째 수까지의 합은 양 끝을 모두 포함한다.

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