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

题目描述

联通块的定义：当且仅当对于两个单元格存在一条以它们中心分别为起点和终点的路径（路径若穿过一 个单元格必然穿过其中心），路径上只包含同一种字符（含起点和终点） ，它们属于同一个联通块。而 这条路径经过的单元格在下面的叙述中如果经过了子矩阵外面的单元格，并且没有只经过子矩阵内部单 元格的满足条件的路径，那么认为这两个单元格不属于同一个联通块。 有一个 n × n 的字符矩阵， q 次操作，单点修改或子矩阵查询。

输入格式

第一行一个正整数 n。 接下来 n 行，每行 n 个小写字母，表示字符矩阵。 接下来一行一个正整数 q，表示操作个数。 接下来 q 行每行先是一个正整数 op，表示操作类型。

修改操作， op = 1，同行接下来两个正整数 x, y 和一个字符 c，表示修改 (x, y) 字符为 c。 · 查询操作， op = 2，同行接下来四个正整数 x1 , y1 , x2 , y2 ，表示子矩阵的左上角字符位置和右下 角字符位置。

输出格式

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

样例

样例 1 输入

1 a 1 2 1 1 1 1

样例 1 输出

1

样例 2 输入

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

样例 2 输出

3 1 2

样例 3 输入

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

样例 3 输出

6 5 3 5

样例 4 见下发文件 ex_biology4.in 和 ex_biology4.ans。该样例满足子任务 19 的限制。 样例 5 见下发文件 ex_biology5.in 和 ex_biology5.ans。该样例满足子任务 20 的限制。

提示

数据范围

子任务编号 n = q = 特殊性质 1 50 2500 A 2 50 2500 A 3 50 5000
4 50 5000
5 100 5000 A 6 100 5000 A 7 100 5000
8 100 5000
9 300 5000 A 10 300 5000
11 500 5000 A 12 500 5000
13 1000 500 A 14 1000 500
15 1000 2500 A 16 1000 2500
17 1000 5000 A 18 1000 5000 A 19 1000 5000 A 20 1000 5000

特殊性质 A：数据保证任何时刻不存在相同字符形成的回路，使得回路内部有不同字符。回路为四联 通。 例如，下面这个图形不符合这个限制：

aaa aba aaa

对于所有数据， 1 ≤ n, m ≤ 1000， 1 ≤ q ≤ 5000，保证 1, 2 操作个数相等。 对于所有数据，保证 KMN 是生竞大神，即使对于 1000 cm ×1000 cm 的培养皿也能准确无误地观测 到每个格子及变化。