The mayor of City A plans to develop a coastal area. This area can be viewed as an $N \times M$ grid. Each cell can be a building, a road, or grass. This area is to be leased to certain companies, but these companies have strange requirements: they require that the buildings leased to them must form a connected component via roads, and each connected component can only be leased to one company. The $N \times M$ grid is composed of characters: O, ., +, |, -. Here, O represents a building, . represents grass, and |, -, + represent roads, which connect the cells above/below, left/right, and all four directions, respectively. Adjacent Os indicate that they are part of the same building. Since the planning might not be optimal, some connected components might consist only of roads; such components cannot be leased! Since part of the land might be developed jointly with other cities, a sub-segment of the $N \times M$ grid will be selected, specifically a sub-grid of size $N' \times M$ ($0 < N' \leq N$). The mayor of City A wants to develop planning software that supports the following functions:

1. Change the content of a cell.
2. Query the number of connected components containing at least one building in a given sub-grid.

Input

The first line contains two integers $N$ and $M$, as described in the problem.

The next $N$ lines each contain $M$ characters representing the initial state of the area.

The next line contains an integer $Q$, representing the number of operations.

The next $Q$ lines each follow one of two formats:

• C i j k: Change the cell at row $i$, column $j$ to character $k$.
• Q l r: Query the number of connected components in the sub-grid from row $l$ to row $r$ (inclusive, spanning columns $1$ to $M$).

Output

For each Q operation, output a single integer on a new line representing the current number of connected components.

Examples

Input 1

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

Output 1

2
1

Subtasks

For $20\%$ of the data, $N = 10^4, Q = 500$.

For another $20\%$ of the data, $M = 1$.

For another $10\%$ of the data, there are no C operations.

For $100\%$ of the data, $1 \leq N \leq 100\,000$, $1 \leq M \leq 6$, $1 \leq Q \leq 10\, 000$.