33OJ
登录 注册

#P17545. [JAG 2026 Summer Camp #2] Robot Damage

[JAG 2026 Summer Camp #2] Robot Damage

Problem Description

A laboratory has a straight test track, which can be regarded as a number line, and a robot that moves along it. At the beginning of each experiment, the robot is stationary at the origin.

Two walls are placed on the track, one at a negative coordinate and the other at a positive coordinate. The robot cannot pass through the walls and can move only within the closed interval between them.

The robot has a button. When the button is pressed, the robot performs the following NN phases in order.

  • Suppose that the robot is at coordinate XX at the beginning of phase ii. It attempts to move along the number line toward coordinate X+ViX+V_i. It moves to the right if Vi>0V_i>0 and to the left if Vi<0V_i<0.
  • If no wall blocks its path, the robot takes one minute to reach its destination. Its speed is zero at the beginning of the phase. It then accelerates and decelerates, reaching the destination at speed zero. Its speed is positive at every intermediate point of the movement.
  • If a wall lies strictly between its current position and its destination, the robot collides with the wall during the movement and ends the phase at the wall.

After completing all NN phases, the robot stops at its current position. If the button is pressed again, it performs the same NN phases again, starting from that position.

Every time the robot collides with a wall at positive speed, it takes one point of damage. However, it takes no damage in either of the following cases.

  • Its destination is exactly at a wall, so it reaches the wall at speed zero.
  • It is already touching a wall at the beginning of a phase and attempts to move beyond that wall. In this case, it does not move.

In other words, the robot takes damage during a phase if and only if a wall lies strictly between its position at the beginning of the phase and its intended destination. The amount of damage does not depend on its speed at the collision, as long as the speed is positive.

You are given QQ queries. The queries are independent. The ii-th query describes the following experiment.

  • Place the walls at coordinates −Wi-W_i and WiW_i, and place the robot at the origin.
  • Press the button a total of TiT_i times, waiting for the previous button press to finish before pressing it again. Do not move the robot between button presses.

Determine the total amount of damage taken by the robot during this experiment.

You are given tt test cases. Solve each of them.

Input Format

The input contains one or more test cases. The first line contains an integer tt, the number of test cases (1≤t≤1051\le t\le 10^5). The descriptions of the test cases follow, each in the following format.

N
V_1 V_2 ... V_N
Q
W_1 T_1
W_2 T_2
...
W_Q T_Q

The integer NN is the number of phases performed on each button press (1≤N≤2×1051\le N\le 2\times 10^5). For each i=1,…,Ni=1,\ldots,N, the integer ViV_i represents the displacement attempted in phase ii (−109≤Vi≤109-10^9\le V_i\le 10^9, Vi≠0V_i\ne 0).

The integer QQ is the number of queries (1≤Q≤2×1051\le Q\le 2\times 10^5). For each i=1,…,Qi=1,\ldots,Q, the integers WiW_i and TiT_i represent the distance from the origin to each wall and the number of button presses, respectively, in the ii-th query (1≤Wi≤10161\le W_i\le 10^{16}, 1≤Ti≤10121\le T_i\le 10^{12}).

The sum of NN over all test cases does not exceed 4×1054\times 10^5. The sum of QQ over all test cases does not exceed 4×1054\times 10^5.

Output Format

For each test case, output QQ lines. The ii-th line should contain the answer to the ii-th query.

4
4
1 -8 6 -7
2
5 1
9 2
3
1 -2 1
1
1 100
2
3 4
2
8 2
8 10000
2
1000000000 -1000000000
1
10 1000000000000
2
2
0
1
1
2000000000000

Hint

In the first test case, query 11 causes collisions at −5-5 in phases 22 and 44, for 22 points of damage. In query 22, both collisions at −9-9 occur during the second button press.

In the second test case, the robot never hits a wall at positive speed, so it takes no damage.