城市规划 ### 题目描述 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)$ 这块地带连通块个数。 其中，$N \leq 10^5, M \leq 6, Q \leq 10000$。 ### 输出描述 对于每个询问中的 $Q$，输出一行，一个数字，表示当前的连通块个数。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 4 .O.. O+O| .O.. ..OO 4 Q 1 4 C 2 4 + C 3 4 | Q 1 4 ``` >输出 ```txt 2 1 ```