#2410 누저크합

26  1 s   128 MB  

Description

N 주어짐, N개의 정수들이 주어짐. a_1 ~ a_N

M 주어짐,

M개의 l, r이 주어짐.

주어진 N개의 정수들에서 M번  a_l ~ a_r범위의 누적합 구하셈.

Input

N <= 1000

M <= 1000

l, r <= 1000

Output

출력

Sample Input

Sample Output

10
1 7 5 4 7 3 6 4 2 9
10
1 2
2 4
3 7
4 10
1 10
1 3
1 4
1 5
1 6
1 7
8
16
25
35
48
13
17
24
27
33