题目描述

现在，总司令需要选出若干小队，进行一场星际战争。

首先，你需要了解小队战斗力定义。一个小队会有两类士兵，我们称为 A 类士兵和 B 类士兵。小队的战斗力为 A 类士兵的数量和 B 类士兵的数量乘积。

B 类士兵接受 $k$ 次能量强化后，会变成 A 类士兵。

初始时，有一个 $n$ 行 $m$ 列的方阵，其中全部是尚未接受能量强化的B类士兵。接下来，向其中投放了$c$次能量强化。每次投放的范围可以被一个矩形描述。投放完成后，每行士兵自动编成一个队伍。

总指挥官接下来制定了 $q$ 个编制军队的方案。一个方案可以被 $x, y$ 表示，即从现在所有的 $n$ 个队伍中选出 $x$ 个队伍，再从这些队伍中各选一个大小为 $y$ 的小队。显然每个小队都可以按上述方法计算小队战斗力，战斗力总和为每个小队的战斗力的和。

你的任务是帮助总司令计算每次编队方案的最大战斗力和。

输入格式

第一行五个数，$n,m,c,k,q$，含义同题目。

接下来 $c$ 行，每行四个数 $x_1, y_1, x_2, y_2$ 描述一个矩阵。

然后有一个空行。

接下来 $q$ 行，每行两个数 $x, y$ 描述一次询问。

输出格式

$q$ 行，每行一个整数表示查询的答案。

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

数据范围

大样例

大样例下载