Maintaining Connectivity in a Grid of Towns

You are given a rectangular grid of size \(n\times m\) which is divided into \(1\times 1\) cells. Each cell is identified by its row and column indices \((i,j)\) (1-indexed) and can initially be one of the following:

• Town (denoted by 'T')
• Fortress (denoted by '#' )
• Empty land (denoted by '.')

Merchants travel among the towns for trade. They can move from one cell to any of its four neighboring cells (up, down, left, and right) provided that the cell does not contain a fortress.

You are required to process \(q\) operations online (i.e. in the order given):

1. 1 r c: Attempt to build a fortress at cell \((r,c)\). It is guaranteed that the cell \((r,c)\) is empty (i.e. contains '.'). Do the following:

   • If, after placing a fortress at \((r,c)\) (i.e. marking it as '#'), every town remains reachable from every other town (i.e. in the grid with allowed cells being towns and empty lands), then the fortress is built (the cell permanently becomes '#' ) and you should output 1.
   • Otherwise, ignore the operation (the cell remains '.') and output 0.

2. 2 r1 c1 r2 c2: Move a town from cell \((r_1,c_1)\) to an adjacent cell \((r_2,c_2)\). It is guaranteed that \((r_1,c_1)\) contains a town ('T') and \((r_2,c_2)\) is empty ('.'), and that \(|r_1-r_2|+|c_1-c_2|=1\).

Connectivity Condition: When checking connectivity, treat a cell as traversable if and only if it does not contain a fortress (i.e. the cell is either empty or contains a town). Note that if there are no towns or only one town in the grid, the connectivity condition is trivially satisfied.

The grid undergoes modifications as operations are applied, and the queries must be processed in the given order.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) (the number of rows, columns, and the number of operations respectively).

The next \(n\) lines each contain a string of length \(m\) representing the initial grid. The characters are:

• 'T' — Town
• '.' — Empty land
• '#' — Fortress

Each of the next \(q\) lines describes an operation in one of the following formats:

• 1 r c
• 2 r1 c1 r2 c2

It is guaranteed that the operations are valid according to the problem statement.

outputFormat

For each operation of type \(1\) (attempting to build a fortress), output a single line with either 1 if the fortress is built or 0 otherwise.

No output is required for operations of type \(2\) (moving a town).

sample

3 3 5
T.T
...
T..
1 2 2
1 3 2
2 1 3 2 3
1 2 1
2 3 1 2 1

1
1
0

</p>