Today in CS class, Zeyu learned about prefixes! For his homework, he is required to create a program to solve the following problem:

Given an array \(A\) consisting of \(N\) integers, and \(Q\) queries, each consisting one integer \(l\), compute the sum of the subarray starting at index \(1\) and ending at index \(l\) (inclusive).

Having not listened in class, Zeyu is unable to solve the problem and comes to you for help. Can you solve it for him?

Subtasks

For this question, Python users are recommended to submit in PyPy instead of Python.

For all subtasks:

\(1 \le N \le 10^3\)

\(-10^9 \le A_i \le 10^9\)

\(1 \le Q \le 10^6\)

\(1 \le l \le N\)

Subtask 1 [40%]

\(1 \le Q \le 10^3\)

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains an integer \(N\), the number of integers in the array.

The second line contains \(N\) space separated integers, denoting the array.

The third line contains an integer \(Q\), the number of queries.

The next \(Q\) lines each contain one integer \(l\), the end index of the subarray.

Output Specification

For each of the \(Q\) queries, output the sum of the subarray starting at index \(1\) and ending at index \(r\) (inclusive) on its own line. To prevent integer overflow, Java and C++ users are recommended to use the long or long long datatype.

Sample Input 1

3
1 2 3
3
1
3
2

Sample Output 1

1
6
3

Sample Output 1 Explanation

For the first query, we are asked to find the sum of the subarray starting at index \(1\) and ending at index \(1\), which is \(A_1 = 1\).

For the second query, we are asked to find the sum of the subarray starting at index \(1\) and ending at index \(3\), which is \(A_1 + A_2 + A_3 = 1 + 2 + 3 = 6\).

For the third and final query, we are asked to find the sum of the subarray starting at index \(1\) and ending at index \(2\), which is \(A_1 + A_2 = 1 + 2 = 3\).