#2874. 训练士兵

题目描述

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

Ryz手下有n*m个士兵，排成一个n行m列的方阵。在一天中，ryz会对士兵下达一些命令，每个命令作用于一个小方阵的所有士兵，并且会增加他们的疲劳值。现在ryz想知道，在一整天训练中，某些小方阵中的士兵的疲劳值总和是多少。

输入格式

第一行有3个整数n,m,k,q。分别表示方阵的行数、列数、指令数和询问数。

接下来k行，每行5个整数x1,x2,y1,y2,s，描述一个指令，表示这条指令对所有坐标(x,y)满足x1<=x<=x2且y1<=y<=y2的士兵产生了s的疲劳值。

(1<=x1<=x2<=n，1<=y1<=y2<=m，0<=s<=1000)

接下来q行，每行2个整数x,y(x,y<=10^9)，描述一个询问，询问是被加密的。一个询问的密码是上一个询问的答案(记为c)，第一个询问的密码是0。询问参数的计算方式如下：

x1=c % n+1,x2=(c+x) % n+1，如果x1>x2则交换x1和x2

y1=c % m+1,y2=(c+y) % m +1，如果y1>y2则交换y1和y2

询问所有坐标(x,y)满足x1<=x<=x2且y1<=y<=y2的士兵的疲劳值总和。

保证答案<2^64。

输出格式

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

样例

样例输入

输入样例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  

样例输出

输出样例1  

  

24  

  

12  

  

46  

  

   

  

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

  

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

  

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

  

   

  

   

  

   

  

   

  

输入样例2  

  

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  

  

   

  

输出样例2  

  

484  

  

0  

  

992  

  

442  

  

304  

数据范围与提示

对于100%的数据 n,m<=10^8,k<=40000,q<=100000；