P1216

训练士兵

训练士兵

Ryz 正在训练一批精锐士兵。

Ryz 手下有 n×mn\times m 名士兵，排列成一个 nn 行 mm 列的方阵。一天中，Ryz 会下达若干条指令。每条指令作用于一个子矩形内的所有士兵，并增加这些士兵的疲劳值。

在一天的训练结束后，Ryz 希望查询若干个子矩形内所有士兵的疲劳值总和。

输入格式

第一行包含四个整数 n,m,k,qn,m,k,q，分别表示方阵的行数、列数、指令数和询问数。

接下来 kk 行，每行包含五个整数 x1,x2,y1,y2,sx_1,x_2,y_1,y_2,s，描述一条指令。该指令会使所有满足 x1≤x≤x2x_1\le x\le x_2 且 y1≤y≤y2y_1\le y\le y_2 的士兵增加 ss 点疲劳值。

如果指令对应的矩形超出 nn 行 mm 列的士兵方阵，则只有该矩形与士兵方阵交集内的士兵受到影响。

接下来 qq 行，每行包含两个整数 x,yx,y，描述一个经过加密的询问。

每个询问的密码为上一个询问的答案，记为 cc；第一个询问的密码为 00。询问矩形的边界按以下方式计算：

x1=c mod n+1,x2=(c+x) mod n+1。x_1=c\bmod n+1,\qquad x_2=(c+x)\bmod n+1。

如果 x1>x2x_1>x_2，则交换 x1x_1 和 x2x_2。

y1=c mod m+1,y2=(c+y) mod m+1。y_1=c\bmod m+1,\qquad y_2=(c+y)\bmod m+1。

如果 y1>y2y_1>y_2，则交换 y1y_1 和 y2y_2。

该询问要求计算所有满足 x1≤x≤x2x_1\le x\le x_2 且 y1≤y≤y2y_1\le y\le y_2 的士兵的疲劳值总和。

输出格式

对于每个询问，输出一行，表示对应矩形内所有士兵的疲劳值总和。

样例输入

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

样例解释

第一次询问的矩形左上角坐标为 (1,1)(1,1)，右下角坐标为 (2,3)(2,3)。

第二次询问的矩形左上角坐标为 (1,3)(1,3)，右下角坐标为 (1,5)(1,5)。

第三次询问的矩形左上角坐标为 (1,3)(1,3)，右下角坐标为 (3,5)(3,5)。

数据范围

  • 对于所有数据，1≤n,m≤1081\le n,m\le 10^8；
  • 1≤k≤4×1041\le k\le 4\times 10^4；
  • 1≤q≤1051\le q\le 10^5；
  • 对于每条指令，1≤x1≤x2≤1081\le x_1\le x_2\le 10^8，1≤y1≤y2≤1081\le y_1\le y_2\le 10^8，0≤s≤1030\le s\le 10^3；
  • 对于每个加密询问，0≤x,y≤1090\le x,y\le 10^9；
  • 保证每个询问的答案严格小于 2642^{64}。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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