题目描述

有$N$个方格排成一行，从左到右编号为$1$到$N$。Snuke和Rng在这些方格上玩一个棋盘游戏，规则如下：

1. 首先，Snuke在每个方格上写入一个整数。
2. 两个玩家各自拥有一个棋子。Snuke将他的棋子放在方格$1$上，Rng将他的棋子放在方格$2$上。
3. 棋子在对手的左边的玩家可以移动自己的棋子。目标方格必须是当前棋子所在方格的右边一个方格，并且不能是对手的棋子所在的方格。
4. 重复步骤3。当无法再移动棋子时，游戏结束。
5. 每个玩家的得分被计算为游戏结束前其棋子所在方格的整数之和。

Snuke已经在方格$i(1≤i≤N-1)$中写入了整数$A_i$，但是尚未写入方格$N$。他决定计算每个整数$X_1,X_2,...,X_M$写入方格$N$并进行游戏时，表达式"(Snuke的分数)-(Rng的分数)"的值。在这里，假设每个玩家移动棋子以使得表达式"(该玩家的分数)-(对手的分数)"的值最大化。

约束条件

• $3≦N≦200,000$
• $0≦A_i≦10^6$
• 所有$A_i$的和至多为$10^6$。
• $1≦M≦200,000$
• $0≦X_i≦10^9$

输入

输入以以下格式从标准输入给出：

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

输出

对于每个整数$X_1,X_2,...,X_M$，如果将其写入方格$N$，则打印表达式"(Snuke的分数)-(Rng的分数)"的值，每行一个。

示例输入 1

5
2 7 1 8
1
2

示例输出 1

0

游戏过程如下图所示，其中S表示Snuke的棋子，R表示Rng的棋子。

两位玩家的得分均为$10$，因此"(Snuke的分数)-(Rng的分数)"的值为$0$。

示例输入 2

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

示例输出 2

2001
6
6
7
7