#916. Prefix sum queries
You get a list, then q queries `l r`. For each query print the sum of a[l..r] (counting from 1, both ends included).
### Input
The first line has n, the second line has n integers separated by spaces. Then q, then q lines l r.
### Output
q lines.
Examples
Input
7 48 23 34 -6 -18 -39 29 3 2 2 7 7 4 4
Output
23 29 -6
Input
12 -45 31 20 -40 -18 33 -46 37 33 2 -27 -31 3 7 12 1 1 12 12
Output
-32 -45 -31
💡 You can solve it with Python, JavaScript or blocks. Read the input line by line with input(). Don't print a question (like input("Number: ")). Print exactly what the output asks for, nothing more.