Connected Blocks Leasing

A coastal development project in City A is represented by an N × M grid. Each cell of the grid can be either a building, a road or a grassland. Buildings are denoted by the character O, grassland by . and roads by one of |, - and +. A road cell with character | connects its top and bottom neighbors; a cell with - connects its left and right neighbors; and a cell with + connects all four directions. Additionally, adjacent O cells form one building.

The companies interested in leasing require that the leased buildings in any connected block are connected via roads. In other words, a connected component (using the connectivity rules below) is eligible for leasing only if it contains at least one building cell (O). Note that a connected component that consists solely of roads is not leasable.

The connectivity between two adjacent cells (neighbors in the four cardinal directions) is defined as follows:

• If both cells are buildings (O), they are always connected.
• If one cell is a building and the other is a road, the connection exists if and only if the road cell has a passage in the direction towards the building. Formally, let d = (dr, dc) be the difference from the building to the road. The road cell must allow passage in the opposite direction (-dr, -dc). For a road cell:
  • If its character is |, it only permits vertical moves, i.e. d must be either (1, 0) or (-1, 0).
  • If its character is -, it only permits horizontal moves, i.e. d must be either (0, 1) or (0, -1).
  • If its character is +, all four directions are allowed.
• If both cells are roads, then the move from the first cell to the second is allowed if the first road cell permits movement in that direction and the second road cell permits movement in the opposite direction.

The city planner’s software must support two types of operations on the grid:

1. Update Operation: Change the character in a specific cell.
2. Query Operation: Given an integer r (with 1 ≤ r ≤ N), consider the subgrid consisting of the first r rows (all M columns) and compute the number of connected components that contain at least one building.
</p>

Input and Output Format: See below.

inputFormat

The first line contains three integers N, M and Q — the number of rows, columns, and operations respectively.

The next N lines each contain a string of length M. Each character is one of O, ., |, - or +, representing the initial grid.

Then follow Q lines, each describing an operation. An operation is given in one of the following two formats:

• 1 i j c — update the cell in row i and column j (1-indexed) to the character c.
• 2 r — query the subgrid consisting of rows 1 to r (inclusive) and all M columns; output the number of connected components (under the connectivity rules) that contain at least one building (O).

It is guaranteed that the operations follow the constraints: 1 ≤ i ≤ N, 1 ≤ j ≤ M, and 1 ≤ r ≤ N.

outputFormat

For each query operation (type 2), output a single integer — the number of connected components (in the specified subgrid) that contain at least one building.

sample

3 3 3
O+.
.|O
O-O
2 2
1 2 2 +
2 3

2
1

</p>