H. Yaser In Baradah
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a well-known river named Baradah. The river is divided into $$$n$$$ sections and at the end of each section there is a fish net. Initially, section $$$i$$$ contains $$$a_{i}$$$ fish and its fish net is closed.

Yaser wants to research the river, The research can be represented by doing $$$Q$$$ operations.

In each operation Yaser chooses a section $$$i$$$ that he has not chosen before and opens its fish net, which causes moving all fish that exist within section $$$i$$$, The fish move forward and stop at the first section whose its fish net is closed. Yaser will not close the fish net after the operation.

After applying each operation, Yaser wants to know the maximum number of fish over all sections.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ $$$( 2 \le n \le 10^{5} )$$$ — the number of sections of Baradah River.

The second line contains $$$n$$$ integers $$$a_1, a_2, .., a_n$$$ $$$( 1 \le a_i \le 10^{9} )$$$ — the number of fish in the $$$i$$$ section.

The third line contains one integer $$$Q$$$ $$$( 1 \le Q \lt n )$$$ — the number of operations

The next $$$Q$$$ lines contain one integer $$$s_i$$$ $$$( 1 \le s_i \le n )$$$ — the section that will be opened in the $$$i$$$-th operation.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$Q$$$ over all test cases do not exceed $$$10^{5}$$$

It is guaranteed that the last section won't be opened during Yaser's operations.

Output

For each test case, Output $$$Q+1$$$ lines, the first line should contain the maximum number of fish over all sections before opening any fish net. Then $$$Q$$$ lines, the $$$i$$$-th line should contain the maximum number of fish over all sections after opening the fish net of the $$$s_i$$$-th section.

Example
Input
1
5
1 2 3 4 5
4
1
2
3
4
Output
5
5
6
10
15