Bessie Painting Subrectangle

Bessie recently received a set of paints. The canvas is represented by a \(N\times M\) rectangular grid where the rows are numbered from 1 to \(N\) and the columns from 1 to \(M\) (\(1\le N,M\le 1000\)). Each cell, when painted, gets a color represented by an uppercase letter from A to Z. Initially, all cells are uncolored and each cell can be painted at most once.

Bessie has predetermined a desired color for each cell. In one brush stroke, she can paint an entire connected component of cells with a single color. Two cells are adjacent if they share a common side.

For example, consider a \(3\times3\) canvas with the following desired colors:

AAB
BBA
BBB

This final pattern requires 4 strokes, because the connected components (by 4-adjacency) in the canvas are:

• The top-left two A's form one component.
• The A in the middle of the second row forms a separate component.
• The B's in the first row (the third column) form their own component.
• The remaining B's form the fourth component.

As a avant‐garde artist, Bessie will only paint a subrectangle of the canvas. She is considering \(Q\) candidate subrectangles (\(1\le Q\le 1000\)). Each candidate is specified by four integers \(x_1, y_1, x_2, y_2\) representing the subrectangle from row \(x_1\) to row \(x_2\) and column \(y_1\) to column \(y_2\). For each candidate, Bessie paints every cell in the subrectangle with its desired color (cells outside remain uncolored). What is the minimum number of strokes required? Note that each candidate is independent of the others.

Note: The time limit of this problem is 1.5 times the default and the memory limit is double the default (512 MB).

inputFormat

The first line contains three integers \(N\), \(M\) and \(Q\) separated by spaces.

The following \(N\) lines each contain a string of length \(M\) consisting of uppercase letters from A to Z, representing the desired color for each cell of the canvas.

Then \(Q\) lines follow, each containing four integers \(x_1\), \(y_1\), \(x_2\) and \(y_2\) (with \(1\le x_1\le x_2\le N\) and \(1\le y_1\le y_2\le M\)), defining a candidate subrectangle.

Sample Input:

3 3 1
AAB
BBA
BBB
1 1 3 3

outputFormat

For each candidate subrectangle, output a single integer on a separate line, representing the minimum number of strokes required to paint that subrectangle.

Sample Output:

4

sample

3 3 1
AAB
BBA
BBB
1 1 3 3

4

</p>