题目背景

Memphis 等一群蒟蒻出题中，花神凑过来秒题……

题目描述

花花山峰峦起伏，峰顶常年被雪，Memphis 打算帮花花山风景区的人员开发一个滑雪项目。

我们可以把风景区看作一个 $n \times n$ 的地图，每个点有它的初始高度，滑雪只能从高处往低处滑【严格大于】。

但是由于地势经常变动【比如雪崩、滑坡】，高度经常变化；同时，政府政策规定对于每个区域都要间歇地进行保护，防止环境破坏。现在，滑雪项目的要求是给出每个 $n \times n$ 个点的初始高度，并给出 $m$ 个命令：

• C a b c 表示坐标为 $(a,b)$ 的点的高度改为 $c$；
• S a b c d 表示左上角为 $(a,b)$ 右下角为 $(c,d)$ 的矩形地区开始进行保护，即不能继续滑雪；
• B a b c d 表示左上角为 $(a,b)$ 右下角为 $(c,d)$ 的矩形地区取消保护，即可以开始滑雪；
• Q 表示询问现在该风景区可以滑雪的最长路径为多少。对于每个 Q 要作一次回答。

花神一看，这不是超简单！立刻秒出了标算~

输入格式

第一行 $n$，第二行开始 $n \times n$ 的地图，意义如上；

接下来一个 $m$，然后是 $m$ 个命令，如上。

输出格式

对于每一个 Q ，输出单独一行的回答。

5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
5
C 1 1 3
Q
S 1 3 5 5
S 3 1 5 5
Q

24
3

样例说明

第一个询问的路线为：$25 \to 24 \to 23 \to 22 \to \cdots \to 3 \to 2$；
第二个询问的路线为：$10 \to 9 \to 2$。

数据规模与约定

• $100\%$ 的数据：$1 \leq n \leq 700$，$1 \leq m \leq 10^6$；

• 其中 Q、S、B 操作总和 $\leq 100$；

• 题中所有数据不超过 $2 \times 10^9$。

题目来源

原创 Memphis