B. Dumb OwlBear
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

OwlBear comes to destroy the village with an ancient-mythical shield in hand.

To protect the village, the villagers had set $$$n$$$ cannons indexed from $$$0$$$ to $$$n-1$$$. Cannon $$$i$$$ $$$(0 \le i \le n-1)$$$ can deal $$$a_i$$$ damage in one shot.At one second, cannons can shoot simultaneously .

OwlBear is full of brute force, so he is not smart. At the $$$k$$$-th second, he uses his shield to protect himself from getting hit by the $$$((k-1) \bmod n)$$$ -th cannon shot.

You need to answer $$$q$$$ queries. Each query gives you an integer $$$h$$$, and you need to find the minimum number of seconds so that villagers can take to deal more or equal to $$$h$$$ damage to the Owlbear.

Input

The first line contains an int $$$t$$$ $$$(1 \le t \le 10^4)$$$, the number of test cases.

Each test case contains the following lines.

The first line contains an int $$$n$$$ $$$(2 \le n \le 10^5)$$$, the number of cannons villagers set.

The second line contains $$$n$$$ integers $$$a_0,a_1,...,a_{n-1}$$$ $$$(1 \le a_i \le 10^{6})$$$, the damage each cannon can deal in one shot.

The third line contains a single integer $$$q$$$ $$$(1 \le q \le 2 \cdot 10^5)$$$, the number of times OwlBear comes to destroy the village.

The next $$$q$$$ lines contain a single integer $$$h$$$ $$$(1 \le h \le 10^{9})$$$, the minimum damage after which OwlBear will run away.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output in a new line  — the minimum number of seconds so that villagers can take to deal more or equal to $$$h$$$ damage to the Owlbear.

Example
Input
1
4
2 3 2 7
4
27
4
120
12
Output
3
1
12
1
Note

For the $$$1$$$-st query, $$$h=27$$$ and $$$a=[2,3,2,7]$$$.

  • After the $$$1$$$-st second, OwlBear will take $$$0+3+2+7=12$$$ damage.
  • After the $$$2$$$-nd second, OwlBear will take $$$2+0+2+7=11$$$ damage.
  • After the $$$3$$$-rd second, OwlBear will take $$$2+3+0+7=12$$$ damage.

The sum of the damages is $$$12+11+12=35$$$, which is greater than $$$h=27$$$.