题目描述

众所周知，徐老师很喜欢玩 《宝可梦》，并且他很喜欢养鲤鱼王

因为鲤鱼王的数量越养越多，他决定开一个大小为 $n * m$ 池塘来专门养鲤鱼王，这个池塘被隔成了 $n * m$ 个格子，每个格子里可以养一只鲤鱼王

现在徐老师准备再次购买 "属性强化果实"，在购买之前他发现了一个更加有效果的道具——"属性强化饲料"，一份饲料可以让一个矩形区间内的鲤鱼王统统受到属性强化

假设一只鲤鱼王从没有受到过强化，当它被强化 $d$ 次以后就会进化成暴鲤龙！

现在徐老师购买了 $c$ 份属性强化饲料，由于他使用饲料的时候手会抖，导致每次能够受到强化的矩阵大小不同，这里我们可以认为徐老师第 $i$ 次使用属性强化饲料时会强化的矩形区间左上角的坐标为 $(x_1,y_1)$，右下角的坐标 $(x_2,y_2)$

接下来需要会需要挑选一些鲤鱼王/暴鲤龙进行组队，为了方便，他制定了如下的组队规则：

1. 以每行为单位，一行内的所有鲤鱼王/暴鲤龙算作一组
2. 设一只宝可梦队伍中有 $A$ 只鲤鱼王，$B$ 只暴鲤龙，该小队的战斗力为 $A * B$
3. 每次询问徐老师会提出两个数字 $a,b$ 作为一次编队，表示需要挑选 $a$ 组，每组中选择 $b$ 只宝可梦组成一队（位置，顺序无关）

现在徐老师想知道，对于每次编队，组成的所有队伍战斗力之和最大是多少？

P.S. 为了方便计算，一开始我们认为池塘里的所有鲤鱼王强化次数均为 $0$

输入格式

输入第一行包含五个整数 $n,m,c,d,q$，含义如题 接下来 $c$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$ 表示这一次使用属性强化饲料的矩阵左上角和右下角 接下来 $q$ 行，每行两个整数 $a,b$ 表示一次编队要求

输出格式

对于每次编队要求，输出该次编队能获得的最大战斗力之和

数据范围

对于所有的数据，保证 $1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq m, 1 \leq a \leq n, 1 \leq b \leq m$

对于编号为 $17 \sim 20$ 的测试数据时间限制为 $2s$

样例输入

5 5 3 2 5
1 1 4 5
3 1 5 3
1 4 5 4
5 3
4 3
4 2
3 3
2 4

样例输出

8
8
4
6
6

样例解释

每只鲤鱼王的强化次数如下：

1 1 1 2 1
1 1 1 2 1
2 2 2 2 1
2 2 2 2 1
1 1 1 1 0

接下来用 $0$ 表示鲤鱼王，用 $1$ 表示暴鲤龙，强化后的池塘内种类如下：

0 0 0 1 0
0 0 0 1 0
1 1 1 1 0
1 1 1 1 0
0 0 0 0 0

对于第一次询问 $5,3$，选 $5$ 组，每组选 $3$ 只： 第一、二组选择 $1$ 只暴鲤龙，$2$ 只鲤鱼王，战斗力各为 $1 * 2 = 2$ 第三、四组选择 $2$ 只暴鲤龙，$1$ 只鲤鱼王，战斗力各为 $2 * 1 = 2$ 第五组只能选择 $3$ 只鲤鱼王战斗力为 $0$ 该方案为最大战斗力之和为 $2 + 2 + 2 + 2 + 0 = 8$

对于第五次询问 $2,4$，选 $2$ 组，每组选 $4$ 只： 第一、二组选择 $1$ 只暴鲤龙，$3$ 只鲤鱼王，战斗力各为 $1 * 3 = 3$ 第三、四组选择 $3$ 只暴鲤龙，$1$ 只鲤鱼王，战斗力各为 $3 * 1 = 3$ 第五组只能选择 $3$ 只鲤鱼王战斗力为 $0$ 选 $2$ 组的最大战斗力之和为 $3 + 3 = 6$