Shefin is playing a video game. In this game, there will be $N$ buildings in a row. $i^{th}$ building has a height of $H_i$ and some gold coins $C_i$ on top of the building. At the beginning of each round, he will land on the top of a random building. When he is on top of a building, he can collect the coins from that building. He can also jump from one building to another. He can jump from $i^{th}$ building to $j^{th}$ building if the $j^{th}$ building is not taller than the $i^{th}$ building and there is no building between these two buildings which is taller than $i^{th}$ building.
There will be a total of $Q$ rounds in the game. You will be given the index of the building on which Shefin will land at the start of each round. You have to tell the maximum amount of gold coins Shefin can collect in that round.
Note that each round is independent i.e. the coins are replenished with original values whenever a new round starts.
Input
Input will start with an integer $T$ denoting the number of testcases in a single line.
Each testcase will start with an integer $N$, the number of buildings in the game. Then there will be $N$ space-separated integers, $i^{th}$ of them is the height of $i^{th}$ building $H_i$. In the next line, there will be another $N$ space-separated integers, $i^{th}$ of them is the amount of gold coins on the top of $i^{th}$ building $C_i$.
The next line will contain an integer $Q$, the number of total rounds. In each of the next $Q$ lines there will be an integer $X_i$ indicating the index of starting building of that round. The buildings are 1-indexed.
Constraints:
Subtask 1(20 points):
$1 \le T \le 5$$1 \le N \le 10$$1 \le H_i \le 3 \times 10^4$$1 \le C_i \le 10^9$$Q = 1$$1 \le X_i \le N$
Subtask 2(30 points):
$1 \le T \le 10$$1 \le N \le 10^3$$1 \le H_i \le 3 \times 10^4$$1 \le C_i \le 10^9$$1 \le Q \le 10^3$$1 \le X_i \le N$
Subtask 3(50 points):
$1 \le T \le 10$$1 \le N \le 10^5$$1 \le H_i \le 3 \times 10^4$$1 \le C_i \le 10^9$$1 \le Q \le 10^5$$1 \le X_i \le N$
Output
For each round, output the maximum number of gold coins Shefin can collect in a single line.
Sample
| Input | Output |
|---|---|
1 6 10 12 8 12 5 8 20 10 22 11 12 11 3 4 1 6 | 44 20 23 |
In the sample input-output:
In the first round: When Shefn starts from index 4, the efficient path will be 4 -> 2 -> 6 -> 5 and thus he will collect 44 gold coins, which is maximum possible.
In the second round: Starting from index 1 , he can't go to any other building because the 2nd building is taller than the 1st building. So he can collect only 20 gold coins from the building in index 1.
In the third round: Starting from index 6, the efficient path will be 6 -> 5 and thus he will be able to collect 23 gold coins, that is maximum possible.
