P12049 KMN の培养皿

 **请仔细阅读提示说明部分。** KMN 是生竞大佬。她有一个培养皿，里面有很多个细胞。每个细胞占据一定的单元格。单元格上会有一个字母表示这个单元格被哪个细胞占据。相同的细胞用相同的字母表示。不同且相邻的细胞用不同的字母表示。 KMN 每次会询问你一个矩形框，如果用这个矩形框去切培养皿，切出来的部分（矩形内部）会包含多少个细胞。如果一个细胞被切成了多份，那么算是多个。 但是，这些细胞也会发生分裂或吞并，所以你还需要维护修改操作。

有一个 $n\times n$ 的有色矩阵 连通块是你熟知的网格图四连通定义：从一个单元格 $A$ 开始，每次走到曼哈顿距离不超过 $1$ 的同色单元格，若能走到另一个单元格 $B$，则这两个单元格 $A,B$ 在同一连通块。 有 $q$ 次操作。 + 单点修改操作：修改单元格 $(x,y)$ 的颜色。 + 区域查询操作：给出 $(l,r,u,d)$，问如果只保留 $[u,d]$ 行与 $[l,r]$ 列交部分的子矩阵，会有多少个连通块。注意：按照上述定义判定两个单元格是否在同一连通块时，不能走到被查询区域之外。 查询操作互相独立。

第一行一个正整数 $n$。 接下来 $n$ 行，每行 $n$ 个小写字母，表示有色矩阵。矩阵中颜色不超过 $26$ 种，分别对应 $26$ 个小写字母。 接下来一行一个正整数 $q$，表示操作个数。 接下来 $q$ 行每行先是一个正整数 $op$，表示操作类型。 + 修改操作，$op=1$，同行接下来两个正整数 $x,y$ 和一个字符 $c$，表示修改 $(x,y)$ 字符为 $c$。 + 查询操作，$op=2$，同行接下来四个正整数 $u, l, d, r$，含义如上。

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

**本题满分为 $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 范围内），以保证后面的询问能正常获得分数。