题目描述

Z 国制作了新型航空炸弹，需要在靶场上测试。靶场是一个 $n \times m$ 的矩形网格区域，每个网格都有初始生命值。测试过程包含两种操作和若干查询：

• 操作 1（补充）：工兵对指定矩形区域的所有网格补充生命值（增加指定值）。
• 操作 0（轰炸）：投下航空炸弹，对指定矩形区域的所有网格削减生命值（减少指定值）。

请根据所有操作后的靶场状态，回答关于指定矩形区域生命值总和的查询。

输入格式

第一行包含四个整数 $n, m, c, q$，分别表示靶场的行数、列数、操作次数、查询次数。

接下来 $n$ 行，每行 $m$ 个整数，代表靶场各网格的初始生命值。

接下来 $c$ 行，每行描述一个操作，格式为：

• 若为补充操作：1 x1 y1 x2 y2 z，表示对左上角为 $(x_1, y_1)$、右下角为 $(x_2, y_2)$ 的矩形区域，每个网格增加 $z$ 点生命值。
• 若为轰炸操作：0 x1 y1 x2 y2 z，表示对左上角为 $(x_1, y_1)$、右下角为 $(x_2, y_2)$ 的矩形区域，每个网格减少 $z$ 点生命值。

最后 $q$ 行，每行四个整数 $a_1, b_1, a_2, b_2$，表示查询左上角为 $(a_1, b_1)$、右下角为 $(a_2, b_2)$ 的矩形区域的生命值总和。

注：所有坐标均从 $1$ 开始。

输出格式

首先输出 $n$ 行，每行 $m$ 个整数，用一个空格隔开，表示所有操作完成后的靶场最终状态。

随后输出 $q$ 行，每行一个整数，依次对应每个查询的结果。

样例

4 4 2 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 2 2 3 3 3
0 1 1 2 2 2
1 1 4 4

-1 -1 1 1
-1 2 4 1
1 4 4 1
1 1 1 1
20

样例解释

1. 初始状态：$4 \times 4$ 网格，每个格子初始生命值为 $1$。
2. 补充操作 1 2 2 3 3 3：对矩形区域 $(2,2)$ 至 $(3,3)$ 的每个格子增加 $3$，该区域 $4$ 个格子变为 $4$。
3. 轰炸操作 0 1 1 2 2 2：对矩形区域 $(1,1)$ 至 $(2,2)$ 的每个格子减少 $2$。
4. 操作后矩阵如上输出。查询 1 1 4 4 即整个矩阵的生命值总和为 $20$。

数据范围

• $1 \leq n, m \leq 2000$
• $1 \leq c, q \leq 10000$
• $1 \leq z \leq 100$
• 初始生命值范围：$1 \leq$ 初始值 $\leq 10$