题目描述

有 $N$ 个格子排成一行，从左到右依次编号为 $1$ 到 $N$。すぬけくん和りんごさん打算用这些格子玩如下的棋盘游戏。

1. 首先，すぬけくん会在每个格子上写一个整数。
2. 两位玩家各自准备一个棋子，すぬけくん将自己的棋子放在第 $1$ 个格子，りんごさん将自己的棋子放在第 $2$ 个格子。
3. 棋子在对方棋子左侧的玩家可以移动自己的棋子。棋子的移动目标必须是当前所在格子右侧、且没有对方棋子的格子。
4. 重复第 3 步，直到没有棋子可以再移动为止，游戏结束。
5. 游戏结束时，每位玩家的得分为其棋子曾经停留过的所有格子上所写整数的总和。

すぬけくん已经在第 $i$ 个格子（$1 \leq i \leq N-1$）上写好了整数 $A_i$，但还没有在第 $N$ 个格子上写整数。现在，すぬけくん有 $M$ 个整数 $X_1, X_2, ..., X_M$，他想分别将这些数写在第 $N$ 个格子上，并计算每种情况下“（すぬけくん的得分）−（りんごさん的得分）”的值。
注意，每位玩家都会采取使“（自己的得分）−（对方的得分）”最大化的走法。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

对于每个 $X_1, ..., X_M$，分别输出将该数写在第 $N$ 个格子时“（すぬけくん的得分）−（りんごさん的得分）”的值，每行输出一个结果。

输入输出样例 #1

输入 #1

5
2 7 1 8
1
2

输出 #1

0

输入输出样例 #2

输入 #2

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

输出 #2

2001
6
6
7
7

说明/提示

限制条件

• $3 \leq N \leq 200,\!000$
• $0 \leq A_i \leq 10^6$
• 所有 $A_i$ 的总和不超过 $10^6$
• $1 \leq M \leq 200,\!000$
• $0 \leq X_i \leq 10^9$