Migrated from Lutece 2935 卡—美—哈—梅—哈——！！！

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 二维线段树 地球遭到了红缎带军团的袭击，卡卡罗特为守护地球奋勇迎战！

卡卡罗特与红缎带军团作战战场可以看作是一个 $n \times n$ 的方格图，从上到下依次为第 $1$ 行、第 $2$ 行 $...$ 第 $n$ 行，从左到右依次为第 $1$ 列、第 $2$ 列 $...$ 第 $n$ 列，坐标 $(x, y)$ 表示第 $x$ 行第 $y$ 列所代表的方格。初始情况下每一块方格内都有若干敌人。

战斗过程中按时间顺序一共发生了 $m$ 个事件，事件有以下 $4$ 种：

• 事件 $1$ ：在坐标 $(x, y)$ 处新增 $k$ 个敌人。
• 事件 $2$ ：卡卡罗特使用龟派气功消灭了第 $x$ 行的所有敌人。
• 事件 $3$ ：卡卡罗特使用龟派气功消灭了第 $y$ 列的所有敌人。
• 事件 $4$ ：卡卡罗特询问当前情况下一个矩形区域内的敌人数量。 矩形用左上角的点 $(x1,y1)$ 和右下角的点 $(x2,y2)$ 表示 。

为了帮助守护地球的战士，你需要实时掌握战场中敌人数量的情况，并在卡卡罗特发出询问时给予正确的回答。

Input

第一行输入三个整数 $n$, $m$，表示战场大小为 $n \times n$，战斗过程中按时间顺序共发生了 $m$ 个事件。

接下来的 $n$ 行每行输入 $n$ 个数，第 $i + 1$ 行输入的第 $j$ 个数 $a_{ij}$ 表示初始情况下坐标 $(i, j)$ 处有 $a_{ij}$ 个敌人。

最后 $m$ 行，每行第一个整数 $opt$ 表示事件发生的类型。

$opt = 1$，之后有三个数 $x, y, k$ ，表示坐标 $(x, y)$ 处新增 $k$ 个敌人；

$opt = 2$，之后有一个数 $x$，表示第 $x$ 行敌人数量清零；

$opt = 3$，之后有一个数 $y$，表示第 $y$ 列敌人数量清零；

$opt = 4$，之后有四个数 $x1, y1, x2, y2$，表示询问的矩形的位置及大小。

Output

对于每一个事件 $4$，输出一个整数表示答案，即询问的矩形区域内敌人的数量。

Samples

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

2
15

Constraints

$1 \leq n \leq 1000$，$1 \leq m \leq 2 \times 10^5$，$0 \leq a_{ij} \leq 1\times 10^3$，$1 \leq x,y,x1,y1,x2,y2 \leq n$，$1 \leq k \leq 1\times10^4$

输入数据均为整数。

Resources

2023 UESTC ICPC Training for Data Structures