[SDOI2013] 城市规划

题目描述

A 市的市长打算在海边开发一段地带。这个地带看成是一个$N \times M$的方格阵。每个格子可以是建筑、道路或者草地。这片地带是要出租给某些公司，但是这些公司的要求很奇怪。他们要求租给他们的建筑要通过道路形成一个连通块。同一个连通块只能租给一家公司。这 个$N\times M$的方格阵是用字符组成的：O，.，+，|，-，其z中O表示建筑，'.' 表示草地。|，-，+表示道路，分别表示把上下，左右、上下左右的格子连起来。相邻的O表示这是一个建筑物。

由于规划可能不太好，可能某些连通块里面只有道路，这里道路是不能出租的！由于最后这块地的选取可能有部分会与其他市共冋开发，所以最后会在这个$N *M$ 中选取一段出来，最后选取出来的是一个$N_i\times M (0<N_1\le N)$的地段。A市的市长想弄要一个规划软件，支持以下功能：

1. 改变一个格
2. 询问某块地带有多少个带建筑的连通块。

输入格式

第一行两个整数 N, M ，如题意所示

接下来的 N 行，每行 M 个字符表示这片地带的初始情况。

接下来的一行一个整数 Q，表示操作次数 就下来的 Q 行，每行有两种格式： C i j k : 把第 i 行第 j 个格子修改成k； Q l r: 询问 (l, 1) (r, M) 这块地带连通块个数。

输出格式

对于每个询问中的 Q，输出一行，一个数字，表示当前的连通块个数

样例 #1

样例输入 #1

4  4
.O..
O+O|
.O.. 
..OO
4
Q 1 4
C 2 4 + 
C 3 4 | 
Q 1 4

样例输出 #1

2 
1

提示

对于 100%的数据， N <= 100000, M <= 6, Q <= 10000