该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

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

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

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

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

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

输出格式

首先输出操作完成后靶场的生命值状态（共 $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×4 网格，每个格子初始生命值为 1。

2. 第一个操作（补充）：1 2 2 3 3 3
   对矩形区域（2≤x≤3，2≤y≤3）的每个格子增加 3 点生命值。该区域包含 4 个格子，每个格子从 1 变为 4。
   操作后矩阵为：

   1 1 1 1
   1 4 4 1
   1 4 4 1
   1 1 1 1
   

3. 第二个操作（轰炸）：0 1 1 2 2 2
   对矩形区域（1≤x≤2，1≤y≤2）的每个格子减少 2 点生命值。该区域包含 4 个格子：

   • (1,1)：1-2=-1，(1,2)：1-2=-1
   • (2,1)：1-2=-1，(2,2)：4-2=2
     操作后矩阵为：

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

4. 查询：1 1 4 4
   计算整个网格的生命值总和：
   $(-1) + (-1) + 1 + 1 + (-1) + 2 + 4 + 1 + 1 + 4 + 4 + 1 + 1 + 1 + 1 + 1 = 20$。

数据范围

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