/* -*- coding: utf-8 -*- * * 440.cc: No.440 2次元チワワ問題 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_H = 500; const int MAX_N = 10000; /* typedef */ typedef long long ll; /* global variables */ string brds[MAX_N]; int y0s[MAX_N], x0s[MAX_N], y1s[MAX_N], x1s[MAX_N]; ll ans[MAX_N]; int dp[MAX_H][MAX_H][MAX_H]; /* subroutines */ /* main */ int main() { int h, w; cin >> h >> w; for (int y = 0; y < h; y++) cin >> brds[y]; int n; cin >> n; for (int i = 0; i < n; i++) { cin >> y0s[i] >> x0s[i] >> y1s[i] >> x1s[i]; y0s[i]--, x0s[i]--, y1s[i]--, x1s[i]--; } for (int y = 0; y < h; y++) for (int x0 = 0; x0 < w; x0++) { int cn = 0, wn = 0; int ww = 0, cw = 0; int cww = 0, wwc = 0; for (int x1 = x0; x1 < w; x1++) { if (brds[y][x1] == 'c') wwc += ww, cn++; else cww += cw, ww += wn, cw += cn, wn++; dp[y][x0][x1] = cww + wwc; } } for (int i = 0; i < n; i++) for (int y = y0s[i]; y <= y1s[i]; y++) ans[i] += dp[y][x0s[i]][x1s[i]]; for (int x = 0; x < w; x++) for (int y0 = 0; y0 < h; y0++) { int cn = 0, wn = 0; int ww = 0, cw = 0; int cww = 0, wwc = 0; for (int y1 = y0; y1 < h; y1++) { if (brds[y1][x] == 'c') wwc += ww, cn++; else cww += cw, ww += wn, cw += cn, wn++; dp[x][y0][y1] = cww + wwc; } } for (int i = 0; i < n; i++) for (int x = x0s[i]; x <= x1s[i]; x++) ans[i] += dp[x][y0s[i]][y1s[i]]; for (int i = 0; i < n; i++) printf("%lld\n", ans[i]); return 0; }