题目背景

众所周知，以津真天世界第一可爱。 ——1jia1

你正在打不氪金手游 yys，这时家长进来了，于是你装作在打数据结构题。

题目描述

由于你在 $n$ 次十连抽后没钱了，于是你应以津真天的邀请去参加一个活动。

这个活动是在一个 $n\times n$ 的矩形区域中进行的，进行若干秒。第 $i$ 秒，主办方会在这个矩形中选择一块小的区域，在每格上面分别撒币。

捡币的规则是这样的：从左上角 $(1,1)$ 出发，走一条抵达 $(n,n)$ 的路径，每次只能从当前格子下面或右边的格子走，并捡起这个区域的金币。

你需要知道，在某一秒某个矩形区域中拥有最多金币的格子有多少金币，某个矩形区域中的金币总数，以及第 $m$ 秒后（如果有撒币操作则先撒币）开始最多能捡多少币。捡币过程中，场上金币数量不会变化，你可以认为这是在 1s 内完成的。

输入格式

第一行，输入整数 $n,m,Q\ (m\leq\text{撒币操作数量})$。

接下来 $Q$ 行，输入五个整数 $u,x1,y1,x2,y2$。（$0<x1\leq x2\leq n$，$0<y1\leq y2\leq n$，$-1\leq u\leq10$）。

• 若 $u>0$，则代表撒币操作，指左上、右下端点分别为 $(x1,y1),(x2,y2)$ 的矩形撒了 $u$ 元的币，撒币的时间依次增加（也就是说第一次撒币操作在第一秒，第二次撒币操作在第二秒，……）。
• 若 $u=0$，则为查大操作，指询问直到上一次撒币操作后，两端点为 $(x1,y1),(x2,y2)$ 的矩形中最大的金币值为多少。（具体意思见题目描述）
• 若 $u=-1$，则为查和操作，指询问直到上一次撒币操作后，两端点为 $(x1,y1),(x2,y2)$ 的矩形中金币值的总和。

输出格式

输出若干行。

前面几行输出一个整数，即每次查询的结果。

最后一行输出你在第$m$秒时，撒完币后捡币能获得的最多的金币。

5 5 7
3 1 1 2 2
5 4 2 5 4
1 2 2 2 4
-1 2 2 4 4
2 2 2 4 3
7 1 4 3 4
0 1 3 5 4

21
8
40

提示

【样例 #1 说明】

数据范围及约定

• Subtask #1（$20$分）：$1\leq n\leq 10$, $1\leq Q\leq 1000$。
• Subtask #2（$20$分）：$1\leq n\leq 1000$, $1\leq Q\leq 10$。
• Subtask #3（$20$分）：$1\leq n\leq 100$, $1\leq Q\leq 1000$。
• Subtask #4（$40$分）：$1\leq n\leq 1000$, $1\leq Q\leq 10000$。