Video Game

tanu_RUET Ada Lovelace National Gir...
Limits 1s, 512 MB

Shefin is playing a game. In this game there are N buildings numbered from 1 to N. Each building has a height of hi. On the top of every building there are some gold coins. The amount of gold coins on the top of the ith building is ai. At the start of a round Shefin will be on the top of the Xth building. He can go to the (X+1)th building from the Xth building, if X < N and the height of the (X + 1)th building is not more than the height of the Xth building. He can also go to the (X - 1)th building if X > 1 and the (X - 1)th building is not taller than the Xth building. Following these rules Shefin will travel through the buildings and collect the gold coins from the top of the buildings. Shefin will play this game for total Q rounds. You will have to tell the maximum amount of gold coin Shefin can collect in each round.

Input

In the first line there will be an integer N, the amount of buildings. Then each of the next N line will contain 2 integers, hi and ai, the height of ith building and the amount of gold coins on the top of ith building.
Then there will be another integer Q and each of the next Q lines will contain an integer X, the number of building from where Shefin will start the ith round.

Constraints:

  • 1 ≤ N ≤ 2*105
  • 0 ≤ hi ≤ 109
  • 0 ≤ ai ≤ 109
  • 1 ≤ Q ≤ 105
  • 1 ≤ X ≤ N

Output

For every round, print the maximum amount of gold coins Shefin can collect on that round.

Sample

InputOutput
10
10 2
10 3
8 4
7 5
8 6
6 9
9 10
10 10
9 100
10 1
10
1
2
3
4
5
6
7
8
9
10
14
14
9
5
15
9
19
110
100
101

Submit

Login to submit.

Statistics

84% Solution Ratio
Annabelle_Earliest, Jan '20
TurinhstuFastest, 0.0s
EgorKulikovLightest, 5.8 MB
jackal_1586Shortest, 632B
Toph uses cookies. By continuing you agree to our Cookie Policy.