#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, q;
short g[N][N];
short h[N][N];
short v[N][N];
bitset<N> Q[N];
struct DSURollBack {
vector<int> e;
void init(int n) {
e = vector<int>(n, -1);
for (int i = 0; i < n; i++)
Q[i / m][i % m] = 1;
}
int get(int x) { return e[x] < 0 ? x : get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
vector<array<int, 4>> mod;
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) {
mod.push_back({-1, -1, -1, -1});
return 0;
}
if (e[x] > e[y]) swap(x, y);
mod.push_back({x, y, e[x], e[y]});
e[x] += e[y], e[y] = x;
Q[y / m][y % m] = 0;
return true;
}
void rollback() {
auto a = mod.back();
mod.pop_back();
if (a[0] != -1) {
e[a[0]] = a[2];
e[a[1]] = a[3];
Q[a[1] / m][a[1] % m] = 1;
}
}
};
struct OfflineDynamicConnectivity {
DSURollBack D;
int sz;
vector<vector<pair<int, int>>> seg;
vector<vector<array<int, 4>>> queries;
vector<int> ans;
void upd(int l, int r, pair<int, int> p) {
if (l > r) return;
for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
if (l & 1) seg[l++].push_back(p);
if (r & 1) seg[--r].push_back(p);
}
}
void process(int ind) {
for (auto& t : seg[ind]) {
D.unite(t.first, t.second);
}
if (ind >= sz) {
int ti = ind - sz;
for (auto& qq : queries[ti]) {
int x1 = qq[0];
int y1 = qq[1];
int x2 = qq[2];
int y2 = qq[3];
int res = 0;
for (int x = x1; x <= x2; x++) {
bitset<N> b = Q[x] << (N - 1 - y2);
b >>= (y1 + N - y2 - 1);
res += b.count();
}
ans.push_back(res);
}
} else {
process(2 * ind); process(2 * ind + 1);
}
for (auto& t : seg[ind]) {
D.rollback();
}
}
void add_query(int ti, array<int, 4> query) {
queries[ti].push_back(query);
}
void init(int max_time) {
sz = 1;
while (sz < max_time) sz *= 2;
seg.assign(2 * sz, {});
queries.assign(sz, {});
D.init(n * m);
}
vector<int> solve() {
process(1);
return ans;
}
};
OfflineDynamicConnectivity O;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
g[i][j] = h[i][j] = v[i][j] = -1;
for (int i = 0; i < n; i++) {
string line; cin >> line;
for (int j = 0; j < m; j++)
g[i][j] = line[j] - 'A';
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == g[i][j + 1])
h[i][j] = 0;
if (g[i][j] == g[i + 1][j])
v[i][j] = 0;
}
}
auto conv = [&](int i, int j) -> int { return i * m + j; };
auto hedge = [&](int i, int j) -> pair<int, int> {
if (g[i][j] != g[i][j + 1])
return {-1, -1};
return {conv(i, j), conv(i, j + 1)};
};
auto vedge = [&](int i, int j) -> pair<int, int> {
if (g[i][j] != g[i + 1][j])
return {-1, -1};
return {conv(i, j), conv(i + 1, j)};
};
O.init(q + 2);
for (int qq = 1; qq <= q; qq++) {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
x1--, y1--, x2--, y2--;
if (x1 != 0) {
for (int y = y1; y <= y2; y++) {
int t = v[x1 - 1][y];
auto e = vedge(x1 - 1, y);
if (e.first != -1) {
O.upd(t, qq - 1, e);
v[x1 - 1][y] = qq + 1;
}
}
}
if (y1 != 0) {
for (int x = x1; x <= x2; x++) {
int t = h[x][y1 - 1];
auto e = hedge(x, y1 - 1);
if (e.first != -1) {
O.upd(t, qq - 1, e);
h[x][y1 - 1] = qq + 1;
}
}
}
if (x2 != n - 1) {
for (int y = y1; y <= y2; y++) {
int t = v[x2][y];
auto e = vedge(x2, y);
if (e.first != -1) {
O.upd(t, qq - 1, e);
v[x2][y] = qq + 1;
}
}
}
if (y2 != m - 1) {
for (int x = x1; x <= x2; x++) {
int t = h[x][y2];
auto e = hedge(x, y2);
if (e.first != -1) {
O.upd(t, qq - 1, e);
h[x][y2] = qq + 1;
}
}
}
O.add_query(qq, {x1, y1, x2, y2});
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (v[i][j] != -1)
O.upd(v[i][j], q + 1, vedge(i, j));
if (h[i][j] != -1)
O.upd(h[i][j], q + 1, hedge(i, j));
}
}
auto ans = O.solve();
for (auto& t : ans)
cout << t << '\n';
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE4gPSAxMDA1OwoKaW50IG4sIG0sIHE7IAoKc2hvcnQgZ1tOXVtOXTsKc2hvcnQgaFtOXVtOXTsKc2hvcnQgdltOXVtOXTsKCmJpdHNldDxOPiBRW05dOwoKc3RydWN0IERTVVJvbGxCYWNrIHsKCiAgICB2ZWN0b3I8aW50PiBlOwoKICAgIHZvaWQgaW5pdChpbnQgbikgewogICAgICAgIGUgPSB2ZWN0b3I8aW50PihuLCAtMSk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIAogICAgICAgICAgICBRW2kgLyBtXVtpICUgbV0gPSAxOwogICAgfQoKICAgIGludCBnZXQoaW50IHgpIHsgcmV0dXJuIGVbeF0gPCAwID8geCA6IGdldChlW3hdKTsgfQogICAgYm9vbCBzYW1lX3NldChpbnQgYSwgaW50IGIpIHsgcmV0dXJuIGdldChhKSA9PSBnZXQoYik7IH0KICAgIGludCBzaXplKGludCB4KSB7IHJldHVybiAtZVtnZXQoeCldOyB9CgogICAgdmVjdG9yPGFycmF5PGludCwgND4+IG1vZDsKCiAgICBib29sIHVuaXRlKGludCB4LCBpbnQgeSkgewogICAgICAgIHggPSBnZXQoeCksIHkgPSBnZXQoeSk7CiAgICAgICAgaWYgKHggPT0geSkgewogICAgICAgICAgICBtb2QucHVzaF9iYWNrKHstMSwgLTEsIC0xLCAtMX0pOwogICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICB9CiAgICAgICAgaWYgKGVbeF0gPiBlW3ldKSBzd2FwKHgsIHkpOwogICAgICAgIG1vZC5wdXNoX2JhY2soe3gsIHksIGVbeF0sIGVbeV19KTsKICAgICAgICBlW3hdICs9IGVbeV0sIGVbeV0gPSB4OwogICAgICAgIFFbeSAvIG1dW3kgJSBtXSA9IDA7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CgogICAgdm9pZCByb2xsYmFjaygpIHsKICAgICAgICBhdXRvIGEgPSBtb2QuYmFjaygpOwogICAgICAgIG1vZC5wb3BfYmFjaygpOwogICAgICAgIGlmIChhWzBdICE9IC0xKSB7CiAgICAgICAgICAgIGVbYVswXV0gPSBhWzJdOwogICAgICAgICAgICBlW2FbMV1dID0gYVszXTsKICAgICAgICAgICAgUVthWzFdIC8gbV1bYVsxXSAlIG1dID0gMTsKICAgICAgICB9CiAgICB9Cn07CgpzdHJ1Y3QgT2ZmbGluZUR5bmFtaWNDb25uZWN0aXZpdHkgewogICAgRFNVUm9sbEJhY2sgRDsKCiAgICBpbnQgc3o7CgogICAgdmVjdG9yPHZlY3RvcjxwYWlyPGludCwgaW50Pj4+IHNlZzsKICAgIHZlY3Rvcjx2ZWN0b3I8YXJyYXk8aW50LCA0Pj4+IHF1ZXJpZXM7CgogICAgdmVjdG9yPGludD4gYW5zOwoKICAgIHZvaWQgdXBkKGludCBsLCBpbnQgciwgcGFpcjxpbnQsIGludD4gcCkgewogICAgICAgIGlmIChsID4gcikgcmV0dXJuOwogICAgICAgIGZvciAobCArPSBzeiwgciArPSBzeiArIDE7IGwgPCByOyBsIC89IDIsIHIgLz0gMikgewogICAgICAgICAgICBpZiAobCAmIDEpIHNlZ1tsKytdLnB1c2hfYmFjayhwKTsKICAgICAgICAgICAgaWYgKHIgJiAxKSBzZWdbLS1yXS5wdXNoX2JhY2socCk7CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgcHJvY2VzcyhpbnQgaW5kKSB7CiAgICAgICAgZm9yIChhdXRvJiB0IDogc2VnW2luZF0pIHsKICAgICAgICAgICAgRC51bml0ZSh0LmZpcnN0LCB0LnNlY29uZCk7CiAgICAgICAgfQogICAgICAgIGlmIChpbmQgPj0gc3opIHsKICAgICAgICAgICAgaW50IHRpID0gaW5kIC0gc3o7IAogICAgICAgICAgICBmb3IgKGF1dG8mIHFxIDogcXVlcmllc1t0aV0pIHsKICAgICAgICAgICAgICAgIGludCB4MSA9IHFxWzBdOwogICAgICAgICAgICAgICAgaW50IHkxID0gcXFbMV07CiAgICAgICAgICAgICAgICBpbnQgeDIgPSBxcVsyXTsKICAgICAgICAgICAgICAgIGludCB5MiA9IHFxWzNdOwogICAgICAgICAgICAgICAgaW50IHJlcyA9IDA7CiAgICAgICAgICAgICAgICBmb3IgKGludCB4ID0geDE7IHggPD0geDI7IHgrKykgewogICAgICAgICAgICAgICAgICAgIGJpdHNldDxOPiBiID0gUVt4XSA8PCAoTiAtIDEgLSB5Mik7CiAgICAgICAgICAgICAgICAgICAgYiA+Pj0gKHkxICsgTiAtIHkyIC0gMSk7CiAgICAgICAgICAgICAgICAgICAgcmVzICs9IGIuY291bnQoKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGFucy5wdXNoX2JhY2socmVzKTsKICAgICAgICAgICAgfQogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHByb2Nlc3MoMiAqIGluZCk7IHByb2Nlc3MoMiAqIGluZCArIDEpOwogICAgICAgIH0KICAgICAgICBmb3IgKGF1dG8mIHQgOiBzZWdbaW5kXSkgewogICAgICAgICAgICBELnJvbGxiYWNrKCk7CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgYWRkX3F1ZXJ5KGludCB0aSwgYXJyYXk8aW50LCA0PiBxdWVyeSkgewogICAgICAgIHF1ZXJpZXNbdGldLnB1c2hfYmFjayhxdWVyeSk7CiAgICB9CgogICAgdm9pZCBpbml0KGludCBtYXhfdGltZSkgewogICAgICAgIHN6ID0gMTsKICAgICAgICB3aGlsZSAoc3ogPCBtYXhfdGltZSkgc3ogKj0gMjsKICAgICAgICBzZWcuYXNzaWduKDIgKiBzeiwge30pOwogICAgICAgIHF1ZXJpZXMuYXNzaWduKHN6LCB7fSk7CiAgICAgICAgRC5pbml0KG4gKiBtKTsKICAgIH0KCiAgICB2ZWN0b3I8aW50PiBzb2x2ZSgpIHsKICAgICAgICBwcm9jZXNzKDEpOwogICAgICAgIHJldHVybiBhbnM7CiAgICB9Cn07CgpPZmZsaW5lRHluYW1pY0Nvbm5lY3Rpdml0eSBPOwoKaW50IG1haW4oKSB7CiAgICBjaW4udGllKDApLT5zeW5jX3dpdGhfc3RkaW8oMCk7CgogICAgY2luID4+IG4gPj4gbSA+PiBxOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSAKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IE47IGorKykKICAgICAgICAgICAgZ1tpXVtqXSA9IGhbaV1bal0gPSB2W2ldW2pdID0gLTE7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsgICAgICAgIAogICAgICAgIHN0cmluZyBsaW5lOyBjaW4gPj4gbGluZTsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG07IGorKykKICAgICAgICAgICAgZ1tpXVtqXSA9IGxpbmVbal0gLSAnQSc7CiAgICB9CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG07IGorKykgewogICAgICAgICAgICBpZiAoZ1tpXVtqXSA9PSBnW2ldW2ogKyAxXSkgCiAgICAgICAgICAgICAgICBoW2ldW2pdID0gMDsKICAgICAgICAgICAgaWYgKGdbaV1bal0gPT0gZ1tpICsgMV1bal0pIAogICAgICAgICAgICAgICAgdltpXVtqXSA9IDA7CiAgICAgICAgfQogICAgfQoKICAgIGF1dG8gY29udiA9IFsmXShpbnQgaSwgaW50IGopIC0+IGludCB7IHJldHVybiBpICogbSArIGo7IH07CgogICAgYXV0byBoZWRnZSA9IFsmXShpbnQgaSwgaW50IGopIC0+IHBhaXI8aW50LCBpbnQ+IHsKICAgICAgICBpZiAoZ1tpXVtqXSAhPSBnW2ldW2ogKyAxXSkgCiAgICAgICAgICAgIHJldHVybiB7LTEsIC0xfTsKICAgICAgICByZXR1cm4ge2NvbnYoaSwgaiksIGNvbnYoaSwgaiArIDEpfTsKICAgIH07CgogICAgYXV0byB2ZWRnZSA9IFsmXShpbnQgaSwgaW50IGopIC0+IHBhaXI8aW50LCBpbnQ+IHsKICAgICAgICBpZiAoZ1tpXVtqXSAhPSBnW2kgKyAxXVtqXSkgCiAgICAgICAgICAgIHJldHVybiB7LTEsIC0xfTsKICAgICAgICByZXR1cm4ge2NvbnYoaSwgaiksIGNvbnYoaSArIDEsIGopfTsKICAgIH07CgogICAgTy5pbml0KHEgKyAyKTsKCiAgICBmb3IgKGludCBxcSA9IDE7IHFxIDw9IHE7IHFxKyspIHsKICAgICAgICBpbnQgeDEsIHkxLCB4MiwgeTI7IGNpbiA+PiB4MSA+PiB5MSA+PiB4MiA+PiB5MjsKICAgICAgICB4MS0tLCB5MS0tLCB4Mi0tLCB5Mi0tOwoKICAgICAgICBpZiAoeDEgIT0gMCkgeyAKICAgICAgICAgICAgZm9yIChpbnQgeSA9IHkxOyB5IDw9IHkyOyB5KyspIHsKICAgICAgICAgICAgICAgIGludCB0ID0gdlt4MSAtIDFdW3ldOwogICAgICAgICAgICAgICAgYXV0byBlID0gdmVkZ2UoeDEgLSAxLCB5KTsKICAgICAgICAgICAgICAgIGlmIChlLmZpcnN0ICE9IC0xKSB7CiAgICAgICAgICAgICAgICAgICAgTy51cGQodCwgcXEgLSAxLCBlKTsKICAgICAgICAgICAgICAgICAgICB2W3gxIC0gMV1beV0gPSBxcSArIDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGlmICh5MSAhPSAwKSB7CiAgICAgICAgICAgIGZvciAoaW50IHggPSB4MTsgeCA8PSB4MjsgeCsrKSB7CiAgICAgICAgICAgICAgICBpbnQgdCA9IGhbeF1beTEgLSAxXTsKICAgICAgICAgICAgICAgIGF1dG8gZSA9IGhlZGdlKHgsIHkxIC0gMSk7CiAgICAgICAgICAgICAgICBpZiAoZS5maXJzdCAhPSAtMSkgewogICAgICAgICAgICAgICAgICAgIE8udXBkKHQsIHFxIC0gMSwgZSk7CiAgICAgICAgICAgICAgICAgICAgaFt4XVt5MSAtIDFdID0gcXEgKyAxOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBpZiAoeDIgIT0gbiAtIDEpIHsKICAgICAgICAgICAgZm9yIChpbnQgeSA9IHkxOyB5IDw9IHkyOyB5KyspIHsKICAgICAgICAgICAgICAgIGludCB0ID0gdlt4Ml1beV07CiAgICAgICAgICAgICAgICBhdXRvIGUgPSB2ZWRnZSh4MiwgeSk7CiAgICAgICAgICAgICAgICBpZiAoZS5maXJzdCAhPSAtMSkgewogICAgICAgICAgICAgICAgICAgIE8udXBkKHQsIHFxIC0gMSwgZSk7CiAgICAgICAgICAgICAgICAgICAgdlt4Ml1beV0gPSBxcSArIDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGlmICh5MiAhPSBtIC0gMSkgewogICAgICAgICAgICBmb3IgKGludCB4ID0geDE7IHggPD0geDI7IHgrKykgewogICAgICAgICAgICAgICAgaW50IHQgPSBoW3hdW3kyXTsKICAgICAgICAgICAgICAgIGF1dG8gZSA9IGhlZGdlKHgsIHkyKTsKICAgICAgICAgICAgICAgIGlmIChlLmZpcnN0ICE9IC0xKSB7CiAgICAgICAgICAgICAgICAgICAgTy51cGQodCwgcXEgLSAxLCBlKTsKICAgICAgICAgICAgICAgICAgICBoW3hdW3kyXSA9IHFxICsgMTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICBPLmFkZF9xdWVyeShxcSwge3gxLCB5MSwgeDIsIHkyfSk7CiAgICB9CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG07IGorKykgewogICAgICAgICAgICBpZiAodltpXVtqXSAhPSAtMSkgCiAgICAgICAgICAgICAgICBPLnVwZCh2W2ldW2pdLCBxICsgMSwgdmVkZ2UoaSwgaikpOwogICAgICAgICAgICBpZiAoaFtpXVtqXSAhPSAtMSkgCiAgICAgICAgICAgICAgICBPLnVwZChoW2ldW2pdLCBxICsgMSwgaGVkZ2UoaSwgaikpOwogICAgICAgIH0KICAgIH0KCiAgICBhdXRvIGFucyA9IE8uc29sdmUoKTsKCiAgICBmb3IgKGF1dG8mIHQgOiBhbnMpIAogICAgICAgIGNvdXQgPDwgdCA8PCAnXG4nOwogICAgCiAgICByZXR1cm4gMDsKfQ==