Given an integer array nums and Q range queries, for each query [left, right] return the sum of elements between indices left and right (inclusive).

Example:

Input array: -2 0 3 -5 2 -1
Queries: 3
0 2
2 5
0 5
Output:
1
-1
-3

Input format: Line 1: space-separated array. Line 2: Q (number of queries). Next Q lines: two integers left right.

Output format: One sum per line.