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

By tanu_RUET · 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


Discussion
Statistics

88% Solution Ratio

Annabelle_Earliest, 2w ago

fire_tornadoFastest, 0.1s

EgorKulikovLightest, 5.8 MB

jackal_1586Shortest, 632B

Submit

Login to submit