题目描述

在“神秘知识守护者”的秘密基地中有一面墙，墙上贴着 $n$ 张矩形海报。这些海报的内部两两不相交。

现在有 $q$ 个新的矩形摆放方案。对于每个查询矩形，需要计算它被现有海报覆盖的面积。

形式化地说：

• 平面上给定 $n$ 个内部互不相交的灰色轴对齐矩形；
• 每次询问给定另一个轴对齐矩形；
• 求询问矩形内部灰色部分的总面积，也就是它与所有已有海报的交面积之和。

由于已有海报内部互不相交，这些交面积之间不会发生重复计数。

部分子任务要求在线回答：后一条询问的真实坐标会依赖前一条询问的答案。

输入格式

第一行包含五个整数 $r,c,n,q,m$：

• $1\le r,c<m\le10^9+9$；
• $0\le n,q\le50000$。

其中：

• $r$：墙的高度；
• $c$：墙的宽度；
• $n$：已有海报数量；
• $q$：询问数量；
• $m$：用于编码查询的模数常数。

接下来 $n$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一张已有海报的两个对角顶点：

• $0\le x_1,x_2\le r$；
• $0\le y_1,y_2\le c$。

所有已有海报的内部两两不相交。

接下来 $q$ 行，每行包含五个整数 $x'_1,y'_1,x'_2,y'_2,v$，每个数都位于 $[0,m-1]$。它们是编码后的查询参数。

设上一条询问的答案为 $l$；对于第一条询问规定 $l=0$。真实坐标按下式得到：

$x_i=(x'_i+l\cdot v)\bmod m$，

$y_i=(y'_i+l\cdot v)\bmod m$，其中 $i\in\{1,2\}$。

保证解码后的坐标满足：

• $0\le x_1,x_2\le r$；
• $0\le y_1,y_2\le c$。

两个给定点是矩形的一对对角顶点，坐标不要求按大小顺序给出。

在标记为 offline 的子任务中，总有 $v=0$，即查询完全不加密。

输出格式

对于每个查询，输出一行一个整数，表示查询矩形与所有已有海报的公共面积总和。

样例 1：离线查询

8 11 3 4 13
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8 0
2 2 4 3 0
3 4 6 7 0
2 9 3 10 0

24
2
6
0

样例 2：在线查询

8 11 3 4 13
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8 4
6 6 8 7 2
2 3 5 6 7
11 5 12 6 5

24
2
6
0

第二个样例描述的是与第一个样例完全相同的真实查询，只是查询坐标使用了在线编码。

子任务