Candies

Time Limit: 2 Seconds

Memory Limit: 65536 KB

Description

As we know, the majority of students in the world-class university like candy and game so much. With some candies, the students are playing a guessing game with you.

These students are standing in a line. Every student has some candies in the hand. (Of course the quantity of the candies will not be negative.) Some kindhearted students will tell you the exactly quantity of candies they have in hand, but some of them won't do that. You may think that THE GAME CAN'T PLAY, but the fact is, every student in line will tell you the exact total quantities of previous one (if exists), himself, and next one (if exists).

You should guess the maximum possible quantity the queried student might have.

Input

The input will consist of multiple testcases.
The first line of each test case is an integer n, indicating the amount of students, 3 ≤ n ≤100000.
The second line contains n integers, the ith number ai represent the exact quantity of candies the ith student has, it will be a nonnegative number not more than 10000, if ai equals to -1, it means that the corresponding student haven't tell you the candies' quantity.
The third line also contains n integers, the ith number represents the sum of ai-1, ai and ai+1 (the first and last student's number contain only two guys' summation).
The forth line contains an integer m, indicating the amount of queries, 1 ≤ m ≤100. Following m integers in a line indicate the 0-base number we queried.

Output

For each test case, you should output exactly m lines, each line contains an integer which is the answer of the corresponding query. If the queried quantity had been told in the input, just output that number.

Sample Input

5
-1 -1 -1 -1 -1 
2 3 3 3 2
2
0 3

Sample Output

2
2

Hint

The quantities they have might be "2 0 1 2 0", "0 2 1 0 2", "1 1 1 1 1" and so on.

Source

None

提交代码