Matrix Color Connectivity

You are given an \(n\times n\) matrix with colored characters. Two cells in the matrix are considered directly connected if they share the same color and are adjacent in one of the four cardinal directions (up, down, left, right). In other words, if you can move from one cell \(A\) to another cell \(B\) by repeatedly moving to an adjacent cell (Manhattan distance \(\le 1\)) that has the same color, then \(A\) and \(B\) belong to the same connected component.

You need to process \(q\) operations. There are two types of operations:

• Point Update: Given coordinates \((x, y)\) and a character \(c\), update the cell at \((x, y)\) to character \(c\).
• Submatrix Query: Given four integers \((l, r, u, d)\), consider the submatrix formed by keeping only the rows \([u, d]\) and columns \([l, r]\). Compute the number of connected components in this submatrix. When determining connectivity, you are only allowed to move within the selected submatrix (i.e. cells outside the query region are not considered).

Operations are processed in order and the queries are independent (each query is evaluated on the current state of the matrix with the restriction of the query submatrix).

Note: Indices are 1-based.

The connectivity is defined using 4-adjacency and all formulas in this statement are expressed in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n \le N,\; 1 \le q \le Q)\) representing the size of the matrix and the number of operations.

The next \(n\) lines each contain a string of length \(n\) representing the initial matrix.

The following \(q\) lines each represent an operation. An operation can be one of the following two types:

• If the line starts with 1, it represents a point update operation and contains: 1 x y c. This operation updates the cell at row \(x\) and column \(y\) to character \(c\).
• If the line starts with 2, it represents a query operation and contains: 2 l r u d. This operation asks for the number of connected components in the submatrix consisting of rows \(u\) to \(d\) and columns \(l\) to \(r\).

outputFormat

For each query operation, output a single integer in a new line: the number of connected components in the specified submatrix.

sample

3 5
abc
abc
abc
2 1 3 1 3
1 2 2 d
2 1 3 1 3
1 3 1 d
2 1 3 2 3

3
5
5