Pushing Robots

题意翻译

在数轴上有 $n$ 个机器人，每个机器人长度为 $1$（即，占据了 $[x_i,x_i+1]$），初始坐标给定。每个机器人被给予了 $k$ 条指令。第 $i$ 个机器人的指令可以用 $k$ 个整数 $f(i,1..k)$ 描述。 在时刻 $t$，机器人 $i$ 会尝试执行指令 $f(i,t\bmod k+1)$。假设第 $i$ 个机器人尝试执行的指令是 $a_i$，我们用以下算法来决定每个机器人的位移方向： - (1) 首先，把每个机器人单独分到自己的 **组** 中，此时共有 $n$ 组。 - (2) 不停重复以下过程： - (2.1) 对于每一组，计算组内机器人指令的和 $S$。如果 $S>0$，我们说该组 **想** 右移；如果 $S<0$，就说该组 **想** 左移。 - (2.2) 如果某一组机器人想右移，而此刻该组之中最靠右的机器人（假设占据 $[v,v+1]$）的右侧段上（$[v+1,v+2]$）有一个不属于这一组的机器人，就把这两组机器人合并。反方向同理。 - (2.3) 如果出现了合并，回到 (2.1)，否则结束第二步。 - (3) 根据 (2) 中的分组结果，如果某一组想左移，就将组内所有机器人左移一个单位，右移同理。特别地，如果有两组，右边一组想左移、左边一组想右移，并且它们中最近的机器人的距离是 $1$（即，左边组中存在一个机器人在 $[v-1,v]$，右边组中存在一个机器人在 $[v+1,v+2]$），则比较两组的 $S$ 的绝对值。如果左边 $\le$ 右边，则右边的左移，左边的不动；否则左边右移，右边不动。 $q$ 次询问 $(t,i)$，求 $t$ 时刻机器人 $i$ 的位置。 $n\le 100,k\le 50,|f_{i,j}|\le 10^6,t\le 10^{18},x_i\le 10^9,q\le 1000$

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

2 1
0 4
1
-1
8
1 0
2 0
1 1
2 1
1 2
2 2
1 3
2 3

输出样例 #1

0
4
1
3
1
2
1
2

输入样例 #2

2 1
0 4
2
-1
8
1 0
2 0
1 1
2 1
1 2
2 2
1 3
2 3

输出样例 #2

0
4
1
3
2
3
3
4

输入样例 #3

2 2
0 1
1 -1
-1 1
4
1 0
1 1
1 2
1 3

输出样例 #3

0
0
-1
0

输入样例 #4

1 3
0
3 -2 1
3
1 5
1 10
1 15

输出样例 #4

1
4
5

输入样例 #5

4 3
-8 -4 2 5
-1 3 0
1 -3 -4
2 -5 2
-1 -4 2
5
3 12
4 18
4 11
1 6
1 10

输出样例 #5

6
9
6
-8
-9