CF1609H.Pushing Robots

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$?

数轴上有 $n$ 个机器人。初始时刻，第 $i$ 个机器人占据单位线段 $[x_i, x_i + 1]$。每个机器人均有一个由 $k$ 条指令组成的程序，指令编号从 $1$ 到 $k$。机器人以循环方式执行这些指令。每条指令用一个整数表示。记第 $i$ 个机器人的第 $j$ 条指令对应的数为 $f_{i, j}$。

机器人的初始位置对应于时刻 $0$。在从时刻 $t$（其中 $0 \le t$）到 $t + 1$ 的一秒钟内，发生如下过程：

1. 每个机器人执行其指令列表中第 $(t \bmod k + 1)$ 条指令。设第 $i$ 个机器人执行的指令对应数值为 $F = f_{i, (t \bmod k + 1)}$。若该数为负（即小于零），则该机器人试图以大小为 $|F|$ 的“力”向左移动；若该数为正（即大于零），则该机器人试图以大小为 $F$ 的“力”向右移动；否则（即 $F = 0$），该机器人不执行任何动作。
2. 我们将机器人想象地划分为若干连续的组，划分方法如下：
   • 初始时，每个机器人自成一组；
   • 对某一组内所有机器人当前所执行指令对应的数值（注意：不取绝对值）求和，记该和为 $S$。我们称该组作为一个整体运动，且其运动“力”为 $S$，运动规则与单个机器人相同：若 $S < 0$，则整组试图以力 $|S|$ 向左移动；若 $S > 0$，则整组试图以力 $S$ 向右移动；若 $S = 0$，则整组不运动；
   • 若某组正在尝试运动，且在其运动方向上紧邻（即其最外侧机器人所占单位线段与另一组最外侧机器人所占单位线段相邻）另一组，则将这两组合并；
   • 重复此合并过程，直至不再有新的合并发生。
3. 每个机器人沿其所属组的运动方向移动 $1$ 个单位长度；若其所属组不运动，则该机器人保持原位。但存在一个例外情形（见下条）。
4. 例外情形：若存在两个机器人组，它们之间恰好相隔一个单位线段，且左侧组试图向右运动、右侧组试图向左运动。记左侧组的指令数值之和为 $S_l$，右侧组的指令数值之和为 $S_r$。此时：
   • 若 $|S_l| \le |S_r|$，则仅右侧组运动；
   • 否则（即 $|S_l| > |S_r|$），则仅左侧组运动。
5. 注意：同一组内的机器人不会粘连在一起，未来仍可能分离。“分组”仅为一种辅助理解机器人在一秒区间 $[t, t + 1]$ 内如何运动的虚拟划分方式。

以下为一秒钟内过程的示意图：

矩形代表机器人，矩形内部数字表示各机器人当前执行的指令数值。最终的分组情况用圆弧标出。图下方显示了机器人移动后的位置。注意：最右侧的两个组中，只有左侧那个组发生了移动。这是因为这两个组彼此相向运动，且它们之间恰好相隔一个单位线段。

请参阅样例以更深入理解整个过程。

你需要回答多个问题：在时刻 $t_i$，第 $a_i$ 个机器人的位置是多少？

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 \lt x_2 \lt \dots \lt x_n \lt 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}$).

第一行包含两个整数 $n$ 和 $k$ —— 机器人数量以及每个机器人程序中的指令数量（$1 \le n \le 100$，$1 \le k \le 50$）。

第二行包含 $n$ 个整数 $x_i$ —— 时刻 $0$ 时各机器人的位置（$-10^9 \le x_1 \lt x_2 \lt \dots \lt x_n \lt 10^9$）。

接下来的 $n$ 行描述了各机器人的程序。其中第 $i$ 行包含 $k$ 个整数 $f_{i, j}$（$|f_{i, j}| \le 10^6$）。

下一行包含一个整数 $q$ —— 需要回答的询问数量（$1 \le q \le 1000$）。

接下来的 $q$ 行每行包含两个整数 $a_i$ 和 $t_i$，表示你需要求出第 $a_i$ 个机器人在时刻 $t_i$ 的位置（$1 \le a_i \le n$，$0 \le t_i \le 10^{18}$）。

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

对于每个问题，在新行输出一个整数：第 $a_i$ 个机器人在时刻 $t_i$ 所占据的单位线段的左边界坐标。