#include using namespace std; #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--) #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair P; // 想定解 // O(H W + Q(H + W)) ll nC2(ll n) { return n * (n - 1) / 2; } class Chiwawa { private: ll N; // 文字列の長さ string s; // 文字列 vector c1; // !!後ろから!! [l, N) vector c2; // 前から [0, r) vector w1; vector w2; vector cw1; vector cw2; vector ww1; vector ww2; vector cww1; vector cww2; public: /*********** 値の設定と前処理 *************/ Chiwawa(string str) { N = str.size(); s = str; if (s == "") return; c1.resize(N + 1, 0); c2.resize(N + 1, 0); w1.resize(N + 1, 0); w2.resize(N + 1, 0); cw1.resize(N + 1, 0); cw2.resize(N + 1, 0); ww1.resize(N + 1, 0); ww2.resize(N + 1, 0); cww1.resize(N + 1, 0); cww2.resize(N + 1, 0); // 後ろから累積和 rrep(i, N) { if (s[i] == 'c') { c1[i]++; cw1[i] += w1[i + 1]; cww1[i] += ww1[i + 1]; } else { w1[i]++; ww1[i] += w1[i + 1]; } c1[i] += c1[i + 1]; w1[i] += w1[i + 1]; cw1[i] += cw1[i + 1]; ww1[i] += ww1[i + 1]; cww1[i] += cww1[i + 1]; } // 前から累積和 rep2(i, 1, N + 1) { if (s[i - 1] == 'w') { w2[i]++; cw2[i] += c2[i - 1]; cww2[i] += cw2[i - 1]; ww2[i] += w2[i - 1]; } else { c2[i]++; } c2[i] += c2[i - 1]; w2[i] += w2[i - 1]; cw2[i] += cw2[i - 1]; ww2[i] += ww2[i - 1]; cww2[i] += cww2[i - 1]; } } // [l, r) に含まれる c の個数を返す(以下同様) ll C(ll l, ll r) { return c1[l] - c1[r]; } ll W(ll l, ll r) { return w1[l] - w1[r]; } ll CW(ll l, ll r) { if (r == N) return cw1[l]; if (l == 0) return cw2[r]; return CW(0, N) - CW(0, l) - CW(r, N) - C(0, l) * W(l, N) - C(l, r) * W(r, N); } ll WW(ll l, ll r) { // ww[l, r) = w[l, r) から2個選ぶ方法の数 return nC2(W(l, r)); } ll CWW(ll l, ll r) { if (r == N) return cww1[l]; if (l == 0) return cww2[r]; return CWW(0, N) - CWW(0, l) - CWW(r, N) - C(0, l) * (WW(l, r) + WW(r, N)) - C(l, r) * WW(r, N) - CW(0, l) * (W(l, r) + W(r, N)) - CW(l, r) * W(r, N) - C(0, l) * W(l, r) * W(r, N); } }; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); /*************** 入力 *****************/ ll H, W; cin >> H >> W; vector rows1(H, ""); // もとの向き vector rows2(H, ""); // 逆向き vector cols1(W, ""); vector cols2(W, ""); rep(i, H) { cin >> rows1[i]; rep(j, W) { cols1[j] += rows1[i][j]; } } rep(i, H) { rows2[i] = rows1[i]; reverse(all(rows2[i])); } rep(j, W) { cols2[j] = cols1[j]; reverse(all(cols2[j])); } // rep(i, H) { // cerr << rows1[i] << endl; // } // cerr << endl; // // rep(j, W) { // cerr << cols1[j] << endl; // } // cerr << endl; // // rep(i, H) { // cerr << rows2[i] << endl; // } // cerr << endl; // // rep(j, W) { // cerr << cols2[j] << endl; // } // cerr << endl; vector rowChiwa1(H, Chiwawa("")); rep(i, H) rowChiwa1[i] = Chiwawa(rows1[i]); vector rowChiwa2(H, Chiwawa("")); rep(i, H) rowChiwa2[i] = Chiwawa(rows2[i]); vector colChiwa1(W, Chiwawa("")); rep(j, W) colChiwa1[j] = Chiwawa(cols1[j]); vector colChiwa2(W, Chiwawa("")); rep(j, W) colChiwa2[j] = Chiwawa(cols2[j]); /*********** クエリへの応答 *************/ ll Q; cin >> Q; rep(q, Q) { ll a, b, c, d; cin >> a >> b >> c >> d; a--; b--; ll ans = 0; rep2(i, a, c) { ans += rowChiwa1[i].CWW(b, d); ans += rowChiwa2[i].CWW(W - d, W - b); // cerr << "rows " << i << ":" << ans << endl; } rep2(j, b, d) { ans += colChiwa1[j].CWW(a, c); ans += colChiwa2[j].CWW(H - c, H - a); // cerr << "cols " << j << ":" << ans << endl; } cout << ans << endl; } }