Problem Description

$ N $ squares are arranged in a row, numbered from $ 1 $ to $ N $ from left to right. Snuke and Ringo are going to play a board game using these squares, as follows:

1. Initially, Snuke writes an integer on each square.
2. Each player prepares a piece, and Snuke places his piece on square $ 1 $, while Ringo places his piece on square $ 2 $.
3. The player whose piece is to the left of the opponent's piece moves their piece. The destination must be to the right of the current square and not occupied by the opponent's piece.
4. Repeat step 3 until no more moves are possible.
5. The sum of the integers on the squares visited by each player's piece is their score.

Snuke has already written integers $ A_i $ on squares $i\ (1≦i≦N-1)$, but has not yet written an integer on square $ N $. Snuke decided to calculate for each of $ M $ integers $ X_1,X_2,...,X_M $ what the result of "Snuke's score - Ringo's score" would be if that number was written on square $ N $. Each player moves their piece to maximize "their score - opponent's score".

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_{N-1} $ $ M $ $ X_1 $ $ X_2 $ $ : $ $ X_M $

Output Format

For each of the $ M $ integers $X_1\ \dots\ X_M$, output one line containing the result of "Snuke's score - Ringo's score" when that number is written on square $ N $.

Sample Input and Output

Sample Input #1

5
2 7 1 8
1
2

Sample Output #1

0

Sample Input #2

9
2 0 1 6 1 1 2 6
5
2016
1
1
2
6

Sample Output #2

2001
6
6
7
7

Notes/Hints

Constraints

• $ 3≦N≦200,000 $
• $ 0≦A_i≦10^6 $
• The sum of $ A_i $ is at most $ 10^6 $.
• $ 1≦M≦200,000 $
• $ 0≦X_i≦10^9 $

Partial Points

• If you solve the dataset where $ M=1 $, you will be awarded $ 700 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 900 $ points.

Sample Explanation 1

The game proceeds as shown in the figure below, where S represents Snuke's piece and R represents Ringo's piece.  Both players score $ 10 $, so "Snuke's score - Ringo's score" is $ 0 $.

见题面 Input 部分

见题面 Output 部分