問題文
ZRK 你收到了RKZ先生送给你的生日棋盘。棋盘是垂直的。 H 方形 * 水平 W 它是一个网格,所有边都与外框平行或垂直。从顶部 i 行,从左起 j 标记列中的方块 (i, j) 。还有,棋盘上的方格 (1, 1) 为黑色,相邻的方块被涂上不同的颜色,如下图所示。
然而,棋盘上的方格大小是扭曲的,从上往下看 i 该行中所有单元格的高度为 a_i,从左起 j 列中的所有单元格具有相同的宽度。 b_j 。 (详情请参考下图。)
ZRK 收到了有缺陷的商品,他说:“左上角的方块是 (px, py) 右下方块是 包含在 (qx, qy) 的矩形中,(黑色矩形的总面积)-(白色矩形的总面积)'' Q 我决定通过玩一个提问游戏来平静自己的心情。为愤怒的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_3 py_3 qx_3 qy_3 ... 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 的整数。
- py_i, qy_i 是 给出了 1 以上 W 的整数。
- px_i \leq qx_i, py_i \leq qy_i 。
小課題
小課題1 [ 30点 ]
- H, W \leq 1 \ 000 很满意。
- Q \leq 5 很满意。
小課題2 [ 120点 ]
- H, W \leq 1 \ 000 很满意。
小課題3 [ 250点 ]
- 没有其他限制。
入力例1
3 3 2 7 35 5 14 9 50 1 1 2 2 1 1 3 2
出力例1
-140 -115
这是问题文本中的图像示例。
例如, 1 第二题,黑色部分的面积为 (7 * 14) + (9 * 35) = 413 白色部分的面积是 (7 * 9) + (14 * 35) = 553 。 (黑色部分的总面积) - (白色部分的总面积) = 413 - 553 = -140 。
入力例2
5 5 5 1 6 15 15 7 14 11 11 5 14 3 5 5 5 2 3 3 4 1 5 3 5 4 3 4 4 2 2 4 3
出力例2
98 54 140 -90 0
作者: 亮2016