暂无测试数据。

我们可以把风景区看成一个 $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$ 行每行 $n$ 个整数表示风景区每个点的高度。

接下来一个数 $m$，表示命令个数。

接下来 $m$ 行，每行描述一个命令，命令的格式见题目描述。

输出格式

对于每一个 $Q$ 命令，单独一行输出一个整数，表示可以滑雪的最长路径是多少。

数据范围

$ 1\le n \le 700, 1 \le m \le 1000000,$ 其中 $Q,S,B$ 命令的次数总和 $\le 100$。

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