AT_tkppc3_d.巨大チェスボード

配点：400 点

ZRK 君在生日当天收到了一份特别的礼物——一块由 Mr.RKZ 送给他的棋盘。这块棋盘由 $H$ 行 $W$ 列的方格组成，其中每条边都与棋盘的外围边框平行或垂直。对于每一个格子，我们用 $(i, j)$ 来表示其所在的行和列。此外，棋盘的左上角格子 $(1, 1)$ 是黑色的，并排的格子颜色不同，就像棋盘的传统棋盘样式。

但是，这块棋盘的格子并不是规则的正方形。第 $i$ 行的所有格子的高度是 $a_i$，而第 $j$ 列的所有格子的宽度为 $b_j$（请参考下图，以便更好地理解这一点）。

ZRK 君收到的这块棋盘存在瑕疵，为了发泄，ZRK 君决定玩一个游戏，让自己心情平复下来。他会针对不同区域进行 $Q$ 次查询，每次查询一个左上角位于 $(px, py)$，右下角位于 $(qx, qy)$ 的矩形区域，计算出区域内「黑色矩形的总面积」减去「白色矩形的总面积」。请帮助心烦意乱的 ZRK 君计算每次查询的结果。

以下是 $a_1=7, a_2=35, a_3=5, b_1=14, b_2=9, b_3=50$ 时棋盘的一个示例图：

输入将通过以下格式给出：

$H$ $W$ $Q$ $a_1$ $a_2$ $a_3$ ... $a_H$ $b_1$ $b_2$ $b_3$ ... $b_W$ $px_1$ $py_1$ $qx_1$ $qy_1$ $px_2$ $py_2$ $qx_2$ $qy_2$ ... $px_Q$ $py_Q$ $qx_Q$ $qy_Q$

输出包含 $Q$ 行。

第 $i$ 行表示左上角为 $(px_i, py_i)$，右下角为 $(qx_i, qy_i)$ 的矩形区域内「黑色矩形总面积」减去「白色矩形总面积」的计算结果。

• $H, W, Q$ 的取值范围在 $1$ 到 $100,000$ 之间。
• $a_i, b_i$ 的取值在 $1$ 到 $10,000$ 之间。
• $px_i, qx_i$ 是从 $1$ 到 $H$ 且满足 $px_i \leq qx_i$ 的整数。
• $py_i, qy_i$ 是从 $1$ 到 $W$ 且满足 $py_i \leq qy_i$ 的整数。

小任务

小任务 1 [30 点]

• 满足 $H, W \leq 1,000$
• 满足 $Q \leq 5$

小任务 2 [120 点]

• 满足 $H, W \leq 1,000$

小任务 3 [250 点]

• 无额外限制。

本翻译由 AI 自动生成