P5620 [DBOI2019] 捡币
题目背景
> 众所周知，以津真天世界第一可爱。
> ——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
输出格式
输出若干行。
前面几行输出一个整数，即每次查询的结果。
最后一行输出你在第$m$秒时，撒完币后捡币能获得的最多的金币。
说明/提示
【样例 #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$。