bzoj#P2874. 训练士兵

训练士兵

题目描述

有一个 n×mn\times m 的矩阵,初始全为 00​。

对其进行 kk 次矩阵加,矩阵加操作 全部完成强制在线 回答 qq 次矩阵和。

输入格式

第一行四个整数 n,m,k,qn,m,k,q

接下来 kk 行,每行五个整数 x1,x2,y1,y2,sx_1,x_2,y_1,y_2,s 表示对以 (x1,y1)(x_1,y_1) 为左上角,(x2,y2)(x_2,y_2) 为右下角的矩阵的每个位置加上 ss

接下来 qq 行,每行两个整数 x,yx,y,询问的矩阵以如下方式进行,记 cc​ 为上一个问题的答案,那么:

x1=cmodn+1,x2=(c+x)modn+1x_1=c\bmod n +1,x_2=(c+x)\bmod n+1,若 x1>x2x_1>x_2 则交换 x1,x2x_1,x_2

y1=cmodm+1,y2=(c+x)modm+1y_1=c\bmod m+1,y_2=(c+x)\bmod m+1,若 y1>y2y_1>y_2 则交换 y1,y2y_1,y_2

询问以 (x1,y1)(x_1,y_1)​ 为左上角,(x2,y2)(x_2,y_2) 为右下角的矩阵的和。

保证答案小于 2642^{64}

输出格式

qq 行,对于每个询问输出一行答案。

4 5 3 3
1 3 2 2 7
2 4 2 3 5
1 4 4 5 6
1 2
0 3
2 2
24
12
46
5 5 5 5
1 1 1 3 242
1 4 4 5 83
3 5 3 3 221
2 2 1 3 254
5 5 2 2 105
0 1
0 4
2 1
1 3
0 1
484
0
992
442
304

样例解释

对于样例 #1,三次询问的矩阵左上角与右下角坐标分别是:

(1,1),(2,3)(1,1),(2,3)

(1,3),(1,5)(1,3),(1,5)

(1,3),(3,5)(1,3),(3,5)

数据规模与约定

对于 100%100\%​ 的数据,1n,m1081\leq n,m\leq 10^81k4×1041\leq k\leq 4\times 10^41q1051\leq q\leq 10^5