在神圣公设守护者的绝密基地深处，有一面墙上贴着许多矩形海报，上面描绘着从他们最宝贵的公设中推导出的深奥知识。这些海报非常稀有，因此它们被放置在互不重叠的位置。

偶尔，一批值得被贴在墙上的新海报会送达。守护者们必须决定将新海报贴在哪里。这是一个复杂的过程，你需要协助他们完成其中一个步骤。

守护者们目前正在为海报挑选候选位置。你需要快速计算出，如果在一个给定的位置贴上一张新海报，当前墙上已有的海报会被覆盖的总面积。

题目描述

给定平面上 $n$ 个互不重叠的灰色矩形。你需要回答 $q$ 个询问，每个询问的形式为：给定一个矩形，其中包含的灰色区域总面积是多少？注意，这不会改变平面上的原有布局。

该答案必须在线生成。

输入格式

第一行包含五个数字 $r, c, n, q, m$ ($1 \le r, c < m \le 10^9 + 9, 0 \le n, q \le 50\,000$)，分别代表墙的高度、宽度、墙上海报的数量、询问的数量以及用于计算询问的模数（下文将解释）。

接下来的 $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$ 之间（含）。你可以使用以下公式计算真实的坐标 $x_1, y_1, x_2, y_2$。

设 $l$ 为上一个询问的答案（对于第一个询问，$l = 0$）。则：

$$x_i = (x'_i + l \cdot v) \pmod m$$ $$y_i = (y'_i + l \cdot v) \pmod m$$

解码后的坐标 $x_1, y_1, x_2, y_2$ 满足以下条件：$0 \le x_1, x_2 \le r, 0 \le y_1, y_2 \le c$。

输出格式

对于每个询问，输出一行，包含一个数字：该询问的答案。

子任务

共有若干个子任务。在离线子任务中，每个询问的 $v$ 值均为零。

样例

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

输出 1

24
2
6
0

说明 1

你可以查看下方的整个平面。

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

输出 2

24
2
6
0

说明 2

这是与上述相同的输入，但使用了在线询问。