Pushing Robots
Contest: Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 3500

There're $$$n$$$ robots placed on a number line. Initially, $$$i$$$-th of them occupies unit segment $$$[x_i, x_i + 1]$$$. Each robot has a program, consisting of $$$k$$$ instructions numbered from $$$1$$$ to $$$k$$$. The robot performs instructions in a cycle. Each instruction is described by an integer number. Let's denote the number corresponding to the $$$j$$$-th instruction of the $$$i$$$-th robot as $$$f_{i, j}$$$.

Initial placement of robots corresponds to the moment of time $$$0$$$. During one second from moment of time $$$t$$$ ($$$0 \le t$$$) until $$$t + 1$$$ the following process occurs:

1. Each robot performs $$$(t \bmod k + 1)$$$-th instruction from its list of instructions. Robot number $$$i$$$ takes number $$$F = f_{i, (t \bmod k + 1)}$$$. If this number is negative (less than zero), the robot is trying to move to the left with force $$$|F|$$$. If the number is positive (more than zero), the robot is trying to move to the right with force $$$F$$$. Otherwise, the robot does nothing.
2. Let's imaginary divide robots into groups of consecutive, using the following algorithm:   Initially, each robot belongs to its own group.  Let's sum up numbers corresponding to the instructions of the robots from one group. Note that we are summing numbers without taking them by absolute value. Denote this sum as $$$S$$$. We say that the whole group moves together, and does it with force $$$S$$$ by the same rules as a single robot. That is if $$$S$$$ is negative, the group is trying to move to the left with force $$$|S|$$$. If $$$S$$$ is positive, the group is trying to move to the right with force $$$S$$$. Otherwise, the group does nothing.  If one group is trying to move, and in the direction of movement touches another group, let's unite them. One group is touching another if their outermost robots occupy adjacent unit segments.  Continue this process until groups stop uniting.
3. Each robot moves by $$$1$$$ in the direction of movement of its group or stays in place if its group isn't moving. But there's one exception.
4. The exception is if there're two groups of robots, divided by exactly one unit segment, such that the left group is trying to move to the right and the right group is trying to move to the left. Let's denote sum in the left group as $$$S_l$$$ and sum in the right group as $$$S_r$$$. If $$$|S_l| \le |S_r|$$$ only the right group will move. Otherwise, only the left group will move.
5. Note that robots from one group don't glue together. They may separate in the future. The division into groups is imaginary and is needed only to understand how robots will move during one second $$$[t, t + 1]$$$.

An illustration of the process happening during one second:

Rectangles represent robots. Numbers inside rectangles correspond to instructions of robots. The final division into groups is marked with arcs. Below are the positions of the robots after moving. Only the left of the two rightmost groups moved. That's because these two groups tried to move towards each other, and were separated by exactly one unit segment.

Look at the examples for a better understanding of the process.

You need to answer several questions. What is the position of $$$a_i$$$-th robot at the moment of time $$$t_i$$$?

Input format:
The first line contains two integer numbers $$$n$$$ and $$$k$$$ — the number of robots and the number of instructions in the program of one robot ($$$1 \le n \le 100$$$, $$$1 \le k \le 50$$$).

The next line contains $$$n$$$ integer numbers $$$x_i$$$ — positions of robots at moment of time $$$0$$$ ($$$-10^9 \le x_1 < x_2 < \dots < x_n < 10^9$$$).

The next $$$n$$$ lines contain descriptions of robots' programs. The $$$i$$$-th of these lines contains $$$k$$$ integer numbers $$$f_{i, j}$$$ ($$$|f_{i, j}| \le 10^6$$$).

The next line contains a single integer number $$$q$$$ — the number of questions you to answer ($$$1 \le q \le 1000$$$).

The next $$$q$$$ lines contain two integer number $$$a_i$$$ and $$$t_i$$$ each, meaning that you should find a position of $$$a_i$$$-th robot at moment of time $$$t_i$$$ ($$$1 \le a_i \le n$$$, $$$0 \le t_i \le 10^{18}$$$).

Output format:
For every question output a single integer on the new line. Coordinate of the left border of unit segment occupied by the $$$a_i$$$-th robot at the moment of time $$$t_i$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2 1
0 4
1
-1
8
1 0
2 0
1 1
2 1
1 2
2 2
1 3
2 3

Example output:
0
4
1
3
1
2
1
2

Example input:
2 1
0 4
2
-1
8
1 0
2 0
1 1
2 1
1 2
2 2
1 3
2 3

Example output:
0
4
1
3
2
3
3
4

Editorial:
First of all, it should be noted, that one iteration of the described algorithm of robots' movements can be implemented in $$$O(n)$$$ time. For example, using stack.
Let's consider moments of time that are multiple of $$$k$$$. And segments of time between such two consecutive moments of time. Consider two adjacent robots. It can be proved that if these two robots touched each other during a segment of time $$$[k \cdot t, k \cdot (t + 1)]$$$ ($$$1 < t$$$), then they will touch each other during any succeeding segment of time $$$[k \cdot t', k \cdot (t' + 1)]$$$ ($$$t < t'$$$). One thing that may change in the future is that the left robot will be blocked from moving to the left, or the right robot will be blocked from moving to the right. Robots just will become closer to each other after such a change. It's also possible that the left robot will be blocked from moving to the right, or the right robot from moving to the left. But then they are touching.
Similarly, if after $$$k$$$ seconds distance between two robots decreases, then it will continue decreasing until they touch during some segment of time. And if two robots touch during a segment of time, then the distance between them after this segment of time will be less than or equal to the distance between them before this segment.
Let's simulate the first $$$k$$$ seconds, and then another $$$k$$$ seconds. Let's look at pairs of adjacent robots.
• If the distance between two robots increased or didn't change, skip this pair.
• If the distance between two robots decreased.   If the distance is $$$\le k \cdot 2 + 1$$$, then robots may touch during the next segment. So, let's simulate the next $$$k$$$ seconds again.  Otherwise, let distance be $$$d$$$ and it decreased by $$$s$$$ during the last segment of time. Then, during the next $$$\lfloor\frac{d - k \cdot 2 - 1}{s}\rfloor$$$ segments of time it will continue decreasing with the same speed ($$$s$$$ units per $$$k$$$ seconds). So we can skip these segments of time, and simulate the next after them.
• If the distance is $$$\le k \cdot 2 + 1$$$, then robots may touch during the next segment. So, let's simulate the next $$$k$$$ seconds again.
• Otherwise, let distance be $$$d$$$ and it decreased by $$$s$$$ during the last segment of time. Then, during the next $$$\lfloor\frac{d - k \cdot 2 - 1}{s}\rfloor$$$ segments of time it will continue decreasing with the same speed ($$$s$$$ units per $$$k$$$ seconds). So we can skip these segments of time, and simulate the next after them.
Let's choose the minimum segment of time that should be simulated. Let's skip all till this segment of time, and simulate it. Then again choose the minimum segment of time till which we can skip simulation.
It can be proved that there will be simulated $$$O(n \cdot k)$$$ segments of time overall. This is due to the fact that there're no more than $$$O(k)$$$ decreases of the distance between two adjacent robots, after which we will do the simulation.
In order to answer questions, let's also simulate segments of time that contain moments of time of questions.
Total time complexity is $$$O(n \cdot k \cdot (n \cdot k + q))$$$.