매일 농부 존은 기르고 있는 소에게 풍부한 영양이 듬뿍담긴 풍부한 양의 꼴을 준다.

그의 노트북에 그 날 먹인 건초더미의 경비를 차례대로 적어둔다. 세금을 낼 시기가 오면 연속적인 구간의 경비의 합을 알아야 한다.

이를 구하는 것이 문제이다.

입력

• 첫 줄에는 두 개의 정수 N 과 Q 가 입력으로 주어진다.(1 <= N,Q <= 500)
• 다음 N 줄에는 각 날의 경비 Hi( 1 <= Hi <= 1000)가 주어진후, 다음 Q 줄에는 정수 쌍 Sj 와 Ej ( 1 <= Sj <= Ej <= N )가 주어진다. Sj 는 시작 , Ej 는 끝 날이다.

출력

입출력 예

입력

4 2
5
8
12
6
1 3
2 4

출력

25
26

보충 설명

• 첫째날 ... 5
• 둘째날 ... 8
• 셋째날 ...12
• 넷째날 ... 6

• 1 3 은 첫째날에서 셋째날 까지의 경비의 합
• 2 4 는 둘째날에서 넷째날 까지의 경비의 합

출처:USACO Dec.2008