글자로 칠하기

Bessie는 최근 그림 도구 세트를 받았다. 캔버스는 $N \times M$ 크기의 칸으로 이루어진 직사각형이다. 행은 위에서 아래로 $1\ldots N$번, 열은 왼쪽에서 오른쪽으로 $1\ldots M$번까지 번호가 매겨진다 ($1\le N,M\le 1000$). 칸을 칠하면 'A'부터 'Z'까지 대문자 하나가 그 칸의 색이 된다. 처음에는 모든 칸이 칠해지지 않은 상태이며, 한 칸은 두 번 이상 칠할 수 없다.

Bessie는 칸마다 원하는 색을 정해 두었다. 같은 색으로 칠할 칸들이 연결 성분을 이루면, 즉 집합 안의 어떤 두 칸이든 인접한 칸들을 따라 서로 오갈 수 있으면 그 집합을 한 번의 붓질로 칠할 수 있다. 두 칸은 변을 공유할 때 인접한다.

예를 들어 아래 $3 \times 3$ 캔버스는 네 번의 붓질로 칠할 수 있다.

AAB
BBA
BBB

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

네 번보다 적은 붓질로는 이 결과를 만들 수 없다.

Bessie는 전위 예술가이므로 캔버스 전체가 아니라 일부 부분 직사각형만 칠한다. 후보 직사각형은 $Q$개($1\le Q\le 1000$)이며, 각 후보는 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$로 주어진다. 이는 행이 $x_1$부터 $x_2$까지, 열이 $y_1$부터 $y_2$까지(양 끝 포함)인 모든 칸으로 이루어진 부분 직사각형을 뜻한다.

각 후보에 대해, 부분 직사각형 안의 모든 칸을 원하는 색으로 칠하고 그 밖의 칸은 칠하지 않은 상태로 두는 데 필요한 붓질의 최소 횟수를 구하라. Bessie는 실제로 칠하지 않으므로 후보들의 답은 서로 독립이다.

첫 줄에 $N$, $M$, $Q$가 주어진다.

이어지는 $N$개의 줄에는 각각 캔버스 한 행의 원하는 색을 나타내는 길이 $M$의 대문자 문자열이 주어진다.

이어지는 $Q$개의 줄에는 각각 후보 부분 직사각형을 나타내는 공백으로 구분된 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다($1\le x_1\le x_2\le N$, $1\le y_1\le y_2\le M$).

$Q$개의 후보마다 답을 한 줄에 하나씩 출력한다.