It is December 24th evening.
An absent minded farmer has just realized
that he did not buy any gift for his wife.
The farmer is on a path in the woods,
and he can only think
about picking up all the mushrooms on the way back home,
praying that that will soften a bit the cries awaiting him.
Suppose the path divided into n segments 1, 2, …n,
and that in each one there are a certain number of mushrooms m_{i}.
The farmer is at the segment f, and his home is at the segment h.
The farmer will pick up all the mushrooms in the segments between f and h.
How many mushrooms will it be?

Input

Input consists of several cases.
Every case begins with n,
followed by the n quantities of mushrooms m_{i}.
Follow the number of queries q about this case,
assuming different positions of the farmer and his home.
Each query consists of f and h, both between 1 and n.
Suppose 1 ≤ n ≤ 10^{5}, 0 ≤ m_{i} ≤ 1000, and q > 0.

Output

For every case, print its number. For every query of every case, print the sum of the numbers between f and h, the extrems inclusive.

Public test cases

**Input**

4 7 0 20 105 3 1 4 3 3 4 3 1 1000 1 1 1

**Output**

#1 132 20 125 #2 1000

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++ Python