건초 비용

농부 존은 매일 소들에게 최고급 건초로 푸짐한 식사를 준다. 그리고 그날 먹인 건초 더미(bale)의 개수를 지출 장부의 다음 줄에 적어 둔다.

세금을 정산할 때가 되자, 존은 건초를 먹인 날짜를 함께 기록해 두지 않았다는 사실을 깨닫는다. 어떤 급여 기록이 어느 달의 지출에 해당하는지 알아내려면, 연속한 며칠 동안 먹인 건초의 합을 여러 번 구해야 한다.

존은 $1$번부터 $N$번까지 번호를 매긴 $N$일치의 자료를 준비했다($4 \le N \le 500$). $i$번째 날에 먹인 건초 더미의 개수는 $H_i$이다($1 \le H_i \le 1{,}000$). 또한 $Q$개의 질의가 있다($1 \le Q \le 500$). 각 질의는 두 정수 $S_j$와 $E_j$로 이루어지며($1 \le S_j \le E_j \le N$), 어떤 날짜 구간의 시작 인덱스와 끝 인덱스를 나타낸다. 각 질의에 대해 $S_j$일부터 $E_j$일까지(양 끝 포함) 먹인 건초 더미 개수의 합을 하나씩 출력하면 된다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $Q$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 $i$번째 날의 건초 더미 개수 $H_i$가 하나씩 주어진다.
• $N+2$번째 줄부터 $N+Q+1$번째 줄까지: $j+N+1$번째 줄에는 $j$번째 질의를 나타내는 두 정수 $S_j$와 $E_j$가 주어진다.

• $1$번째 줄부터 $Q$번째 줄까지: $j$번째 줄에는 $S_j$일부터 $E_j$일까지의 건초 더미 개수의 합을 정수 하나로 출력한다.

각 질의 $S_j \dots E_j$에 대해, $S_j$일부터 $E_j$일까지의 건초 개수를 모두 더하면 된다. 누적 합(prefix sum) 배열을 미리 만들어 두면 각 질의를 상수 시간에 처리할 수 있다.