Description

有一个 $n\times n$ 的有色矩阵

连通块是你熟知的网格图四连通定义：从一个单元格 $A$ 开始，每次走到曼哈顿距离不超过 $1$ 的同色单元格，若能走到另一个单元格 $B$，则这两个单元格 $A,B$ 在同一连通块。

有 $q$ 次操作。

• 单点修改操作：修改单元格 $(x,y)$ 的颜色。
• 区域查询操作：给出 $(l,r,u,d)$，问如果只保留 $[u,d]$ 行与 $[l,r]$ 列交部分的子矩阵，会有多少个连通块。注意：按照上述定义判定两个单元格是否在同一连通块时，不能走到被查询区域之外。

查询操作互相独立。

Input Format

第一行一个正整数 $n$。
接下来 $n$ 行，每行 $n$ 个小写字母，表示有色矩阵。矩阵中颜色不超过 $26$ 种，分别对应 $26$ 个小写字母。

接下来一行一个正整数 $q$，表示操作个数。
接下来 $q$ 行每行先是一个正整数 $op$，表示操作类型。

• 修改操作，$op=1$，同行接下来两个正整数 $x,y$ 和一个字符 $c$，表示修改 $(x,y)$ 字符为 $c$。
• 查询操作，$op=2$，同行接下来四个正整数 $u, l, d, r$，含义如上。

Output Format

$q\div 2$ 行每行一个正整数表示答案。保证 $2$ 类操作恰好占到一半。

1
a
1
2 1 1 1 1

1

4
aabb
aaaa
aaaa
bbaa
3
2 1 1 4 4
2 2 2 3 3
2 1 1 2 4

3
1
2

5
aaaaa
ababa
aabaa
ababa
aaaaa
9
2 1 1 5 5
1 3 3 a
2 1 1 5 5
1 2 3 b
1 4 3 b
1 3 2 b
1 3 4 b
2 1 1 5 5
2 3 1 3 5

6
5
3
5

Hint

本题满分为 $3\times 10^5$ 分。
对于 $100\%$ 的数据：
$1\le l,r,u,d\le n\le 500$。
$1\le q\le 5000$。

保证 $1,2$ 操作个数相等。
本题 SubTask 只是为了把同规模数据分到一起，不存在捆绑关系。
测试点信息
|SubTask 编号|$n=$|$q=$| |:-:|:-:|:-:| |$1$|$50$|$1000$| |$2$|$50$|$5000$| |$3$|$100$|$1000$| |$4$|$100$|$5000$| |$5$|$300$|$1000$| |$6$|$300$|$3000$| |$7$|$300$|$5000$| |$8$|$500$|$1000$| |$9$|$500$|$3000$| |$10$|$500$|$5000$|

对于 $100\%$ 的数据，保证 KMN 是生竞大神，即使对于 $500\operatorname{cm}\times500\operatorname{cm}$ 的培养皿也能准确无误地观测到每个格子及变化。
本题采用 Special Judge。当一个测试点有 $x$ 次 II 类操作时对于一次 II 类操作，若您的答案和标准答案一致，那么您获得 $\frac{10000}{x}$ 的分数。
因此，若您的程序无法解决某次查询问题，请输出一行单个整数（需在 int 范围内），以保证后面的询问能正常获得分数。