数轴上放置了 $$$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$$$ 向右移动。否则,机器人什么也不做。
2. 让我们使用以下算法将机器人想象地分成连续的组: 最初,每个机器人属于自己的组。 让我们总结一组机器人指令对应的数字。请注意,我们对数字进行求和,而不是取绝对值。将该总和表示为 $$$S$$$。我们说整个群体一起移动,并按照与单个机器人相同的规则用力 $$$S$$$ 进行移动。也就是说,如果 $$$S$$$ 为负数,则该群体试图用力 $$$|S|$$$ 向左移动。如果 $$$S$$$ 为正,则该群体正试图用力 $$$S$$$ 向右移动。否则,该小组什么也不做。 如果一个群体试图移动,并且在移动方向上接触到另一群体,那么让我们将他们联合起来。如果一组最外面的机器人占据相邻的单元段,则一组正在接触另一组。 继续这个过程,直到群体停止团结。
3. 每个机器人沿着其组的移动方向移动$$$1$$$,或者如果其组不移动则保持在原地。但有一个例外。
4. 例外情况是,如果有两组机器人,正好被一个单位段划分,则左侧组尝试向右移动,右侧组尝试向左移动。我们将左侧组中的总和表示为 $$$S_l$$$,将右侧组中的总和表示为 $$$S_r$$$。如果$$$|S_l| \le |S_r|$$$ 只有正确的组才会移动。否则,只有左边的组会移动。
5. 请注意,一组机器人不会粘在一起。他们将来可能会分开。分组的划分是虚构的,仅需要了解机器人在一秒钟内如何移动 $$$[t, t + 1]$$$。
一秒钟内发生的过程的图示:
矩形代表机器人。矩形内的数字对应于机器人的指令。最终分组用弧线标记。以下是机器人移动后的位置。最右边的两组中只有左边的动了。这是因为这两群人试图靠近对方,结果却被恰好隔开了一个单位段。
查看示例以更好地理解该过程。
您需要回答几个问题。第 $$$a_i$$$ 个机器人在 $$$t_i$$$ 时刻的位置是什么?
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ - 机器人数量和一个机器人程序中的指令数量($$$1 \le n \le 100$$$、$$$1 \le k \le 50$$$)。
下一行包含 $$$n$$$ 整数 $$$x_i$$$ — 机器人在 $$$0$$$ 时刻的位置 ($$$-10^9 \le x_1 < x_2 < \dots < x_n < 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$$$,这意味着您应该在 $$$t_i$$$ 时刻找到第 $$$a_i$$$ 个机器人的位置 ($$$1 \le a_i \le n$$$, $$$0 \le t_i \le 10^{18}$$$)。
输出
对于每个问题,在新行上输出一个整数。第$$$a_i$$$个机器人在$$$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