Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Video Game Pro

By tanu_RUET · Limits 3s, 512 MB

Shefin is playing a video game. In this game, there will be NN buildings in a row. ithi^{th} building has a height of HiH_i and some gold coins CiC_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 ithi^{th} building to jthj^{th} building if the jthj^{th} building is not taller than the ithi^{th} building and there is no building between these two buildings which is taller than ithi^{th} building.

There will be a total of QQ 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 TT denoting the number of testcases in a single line.

Each testcase will start with an integer NN, the number of buildings in the game. Then there will be NN space-separated integers, ithi^{th} of them is the height of ithi^{th} building HiH_i. In the next line, there will be another NN space-separated integers, ithi^{th} of them is the amount of gold coins on the top of ithi^{th} building CiC_i.

The next line will contain an integer QQ, the number of total rounds. In each of the next QQ lines there will be an integer XiX_i indicating the index of starting building of that round. The buildings are 1-indexed.

Constraints:

Subtask 1(20 points):

  • 1T51 \le T \le 5
  • 1N101 \le N \le 10
  • 1Hi3×1041 \le H_i \le 3 \times 10^4
  • 1Ci1091 \le C_i \le 10^9
  • Q=1Q = 1
  • 1XiN1 \le X_i \le N

Subtask 2(30 points):

  • 1T101 \le T \le 10
  • 1N1031 \le N \le 10^3
  • 1Hi3×1041 \le H_i \le 3 \times 10^4
  • 1Ci1091 \le C_i \le 10^9
  • 1Q1031 \le Q \le 10^3
  • 1XiN1 \le X_i \le N

Subtask 3(50 points):

  • 1T101 \le T \le 10
  • 1N1051 \le N \le 10^5
  • 1Hi3×1041 \le H_i \le 3 \times 10^4
  • 1Ci1091 \le C_i \le 10^9
  • 1Q1051 \le Q \le 10^5
  • 1XiN1 \le X_i \le N

Output

For each round, output the maximum number of gold coins Shefin can collect in a single line.

Sample

InputOutput
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.

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.