维持岛屿的光芒已开始颤动，曾经和谐塑造万物的四种元素如今正相互干扰彼此的流动。

元素流曾经以完美的比例融合，如今却已失去秩序，在土地上留下了零散的痕迹。

人们试图恢复平衡，但他们的努力轻易地白费了——他们精心重建的结构一次又一次地崩塌。

见证他们为维护元素和谐所做的最后尝试。追随他们的足迹，恢复他们奋斗到最后一刻所保护的微妙秩序。

岛屿上铺设着一个刻有四种元素的网格：土（Earth）、水（Water）、火（Fire）和风（Air）。

该网格的大小为 $N \times M$，每个单元格包含四种元素之一。从上往下数第 $r$ 行、从左往右数第 $c$ 列的单元格表示为 $(r, c)$。

每种元素由两个属性定义：温度（temperature）和湿度（humidity），如下表所示：

每当网格中任意 $2 \times 2$ 的正方形内出现所有四种元素时，它们的属性就会达到完美平衡。这样的正方形被称为和谐正方形。在下面的例子中，绿色高亮的两个区域都是和谐正方形。

然而，最近岛民们观察到元素流的稳定性日益下降。一种现象发生了 $Q$ 次，每次都会改变一个特定矩形区域内的元素。在每种情况下，受影响的元素都会转变为具有相反温度或湿度属性的对应元素。

例如，如果将下图网格中心 $3 \times 3$ 区域内的元素更改为具有相反温度属性的元素，网格将按如下方式转换：

岛民们希望确定每次对网格进行修改后，网格中存在的和谐正方形的数量。

输入格式

第一行包含三个空格分隔的整数 $N$、$M$ 和 $Q$，分别表示网格的大小和修改的次数。

接下来的 $N$ 行，每行包含 $M$ 个字符 $B_{i1}, B_{i2}, \dots, B_{iM}$。每个字符为 E、W、F、A 之一，分别代表 Earth（土）、Water（水）、Fire（火）和 Air（风）。

接下来的 $Q$ 行，每行包含五个整数 $t_i, r_{1i}, c_{1i}, r_{2i}, c_{2i}$，表示对网格进行的修改。$t_i$ 表示网格修改的类型，其中 $t_i = 1$ 表示温度属性改变，$t_i = 2$ 表示湿度属性改变。其余四个整数表示修改发生在所有满足 $r_{1i} \le r \le r_{2i}$ 且 $c_{1i} \le c \le c_{2i}$ 的单元格 $(r, c)$ 上。

• $2 \le N \le 1000$
• $2 \le M \le 1000$
• $0 \le Q \le 10^4$
• $B_{ij}$ 是 E、W、F、A 之一（$1 \le i \le N, 1 \le j \le M$）
• $1 \le t_i \le 2$（$1 \le i \le Q$）
• $1 \le r_{1i} \le r_{2i} \le N$（$1 \le i \le Q$）
• $1 \le c_{1i} \le c_{2i} \le M$（$1 \le i \le Q$）

输出格式

第一行输出一个整数，表示网格初始状态下和谐正方形的数量。

然后，对于 $Q$ 次修改中的每一次，输出一行包含一个整数，表示应用该修改后网格中和谐正方形的数量。

子任务

• 子任务 1（6 分）：$Q = 0$
• 子任务 2（7 分）：$N \le 100$，$M \le 100$，$Q \le 100$
• 子任务 3（31 分）：$r_{1i} = r_{2i}$（$1 \le i \le Q$）
• 子任务 4（8 分）：$r_{1i} = c_{1i} = 1$，$r_{2i} = N$，$c_{2i} = M$（$1 \le i \le Q$）
• 子任务 5（48 分）：无附加限制。

样例

输入样例 1

5 5 2
EEAFW
FWEWA
WFEAF
AFAWE
EWEAF
1 2 2 4 4
2 2 1 4 5

输出样例 1

5
2
2

输入样例 2

4 6 0
EWEWFA
FAFAEW
WEEWFA
FAWFFA

输出样例 2

10