题目描述

石老师信奥班里有一个数学天才，XYZ！XYZ经常口算出很难的数学题，搞得大家都十分的崇拜他！

石老师想要考验一下XYZ的智商，于是出了一道很难的题：石老师给出 N 个整数，让XYZ分组。要求必须从第一个数开始分组，并且每组必须是连续的一段数，每组的数字个数不一定相同，但是要求每组和相等，XYZ需要求出每组和最小可以是多少。（当然这些数一定可以被分组，大不了直接分成一组。）

只需1秒钟，XYZ就说出了他的答案！打了石老师一个措手不及，于是石老师请你用计算机算出答案。

输入格式

第一行为一个数 N；

第二行为 N 个整数（每个数均小于等于 1000 ），两个数间用空格隔开。

第三行为一个数 $M$；

第四行为 $M（\le10）$ 个整数表示第二行中的所有数循环左移 $b_i（\le10^9）$得到的序列的最小分组和。

输出格式

$M$行，一行一个最小的和。

数据范围

$1\leq n\leq 1000000$。

样例数据

输入:

6
2 5 1 3 3 7
6
0
1
2
3
4
5

输出:

7
21
7
21
21
7

解释:

分成三组 (2，5)(1，3，3)(7) 和为 7，不存在比 7 更小的和。

也可能只能分成一组。