A市的市长打算在海边开发一段地带。这个地带看成是一个 N×M 的方格阵。每个格子可以是建筑、道路或者草地。这片地带是要出租给某些公司,但是这些公司的要求很奇怪, 他们要求租给他们的建筑要通过道路形成一个连通块,同一个连通块只能租给一家公司。这个 N×M 的方格阵是用字符组成的:O
,.
,+
,|
,-
。其中 O
表示建筑。表示 .
草地。|
,-
,+
表示道路,分别表示把上下,左右,上下左右的格子连起来。相邻的 O
表示这是一个建筑物。由于规划可能不太好,可能某些连通块里面只有道路,这里道路是不能出租的!由于最后这块地的选取可能有部分会与其他市共同开发,所以最后会在这个 N×M 中选取一段出来,最后选取出来的是一个 N′×M(0<N′≤N)的地段。A市的市长想要弄一个规划软件,支持以下功能:
- 改变一个格子。
- 询问当前某块地带有多少个带建筑的连通块。
输入格式
第一行两个整数 N,M ,如题意所示。
接下来的 N 行,每行 M 个字符表示这片地带的初始情况。
接下来的一行一个整数 Q,表示操作次数。
接下来的 Q 行,每行有两种格式:
C i j k
: 把第 i 行第 j 个格子修改成 k 。Q l r
: 询问 (l,1) (r,M) 这块地带连通块个数 。
输出格式
对于每个询问中的 Q
,输出一行,一个数字,表示当前的连通块个数。
样例数据
样例输入
4 4
.O..
O+O|
.O.. ..OO
4
Q 1 4
C 2 4 +
C 3 4 |
Q 1 4
样例输出
2
1
子任务
对于 20% 的数据,N=104,Q=500。
另有 20% 的数据,M=1。
另有 10% 的数据,不存在 C
操作。
对于 100% 的数据,1≤N≤100000,1≤M≤6,1≤Q≤10000。