Challenge: Range Sum Questions

Lab Python Beginner 10 points

Read a list of numbers, then q questions. Each question gives i j: print the sum of the items from index i to j (both included, starting at 0). Use a prefix sum list.

Input

Line 1: whole numbers. Line 2: q. Then q lines with i j.

Output

One total per question.

Example

Input

Output

10
19
7

Sample input available Sample output available

Editor

Python

Hints

prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i].

sum(i..j) = prefix[j + 1] - prefix[i].

Solution explanation

Building the prefix list is O(n); then every question is answered in O(1).

Show solution

nums = list(map(int, input().split()))
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
q = int(input())
for _ in range(q):
    i, j = map(int, input().split())
    print(prefix[j + 1] - prefix[i])

Output

Answer