#include #include using namespace std; using namespace atcoder; #ifdef _MSC_VER #include #endif using ll = long long; using ld = long double; using ull = unsigned long long; using P = pair; //#define endl "\n" #define rep1(i, n) for (ll i = 0; i < (ll)(n); i++) #define rep2(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) #define OVERLOAD_REP(_1, _2, _3, name, ...) name #define rep(...) OVERLOAD_REP(__VA_ARGS__, rep2, rep1)(__VA_ARGS__) #define rrep(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--) #define all(s) (s).begin(), (s).end() #define fi first #define se second const ll mod = 998244353; const ll inf = 4000000000000000000ll; const ld eps = ld(0.00000000001); static const long double pi = 3.141592653589793; templatevoid vcin(vector &n){for(int i=0;i>n[i];} templatevoid vcin(vector &n,vector &m){for(int i=0;i>n[i]>>m[i];} templatevoid vcout(vector &n){for(int i=0;ivoid vcin(vector> &n){for(int i=0;i>n[i][j];}}} templatevoid vcout(vector> &n){for(int i=0;ivoid print(pair a){cout<auto min(const T& a){ return *min_element(all(a)); } templateauto max(const T& a){ return *max_element(all(a)); } templatebool chmax(T &a,const U b) { if (abool chmin(T &a,const U b) { if (b void ifmin(T t,T u){if(t>u){cout<<-1< void ifmax(T t,T u){if(t using V = vector; template using VV = V>; template using VVV = V>>; template auto mvec(T val, ll n) { return V(n, val); } template auto mvec(T val, ll n, Args... args) { return V(n, mvec(val, args...)); } vector divisor(ll x){ vector ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / i);}}}sort(all(ans)); return ans; } ll pop(ll x){return __builtin_popcountll(x);} ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;} void cincout(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout<< fixed << setprecision(15); } #pragma once template struct SegmentTree2D { private: int id(int h, int w) const { return h * 2 * W + w; } public: int H, W; vector seg; const F f; const T I; SegmentTree2D(int h, int w, F _f, const T& i) : f(_f), I(i) { init(h, w); } void init(int h, int w) { H = W = 1; while (H < h) H <<= 1; while (W < w) W <<= 1; seg.assign(4 * H * W, I); } // build にのみ呼ぶ void set(int h, int w, const T& x) { seg[id(h + H, w + W)] = x; } void build() { // w in [W, 2W) for (int w = W; w < 2 * W; w++) { for (int h = H - 1; h; h--) { seg[id(h, w)] = f(seg[id(2 * h + 0, w)], seg[id(2 * h + 1, w)]); } } // h in [0, 2H) for (int h = 0; h < 2 * H; h++) { for (int w = W - 1; w; w--) { seg[id(h, w)] = f(seg[id(h, 2 * w + 0)], seg[id(h, 2 * w + 1)]); } } } T get(int h, int w) const { return seg[id(h + H, w + W)]; } T operator()(int h, int w) const { return seg[id(h + H, w + W)]; } void update(int h, int w, const T& x) { h += H, w += W; seg[id(h, w)] = x; for (int i = h >> 1; i; i >>= 1) { seg[id(i, w)] = f(seg[id(2 * i + 0, w)], seg[id(2 * i + 1, w)]); } for (; h; h >>= 1) { for (int j = w >> 1; j; j >>= 1) { seg[id(h, j)] = f(seg[id(h, 2 * j + 0)], seg[id(h, 2 * j + 1)]); } } } T _inner_query(int h, int w1, int w2) { T res = I; for (; w1 < w2; w1 >>= 1, w2 >>= 1) { if (w1 & 1) res = f(res, seg[id(h, w1)]), w1++; if (w2 & 1) --w2, res = f(res, seg[id(h, w2)]); } return res; } // [ (h1,w1), (h2,w2) ) 半開 T query(int h1, int w1, int h2, int w2) { if (h1 >= h2 || w1 >= w2) return I; T res = I; h1 += H, h2 += H, w1 += W, w2 += W; for (; h1 < h2; h1 >>= 1, h2 >>= 1) { if (h1 & 1) res = f(res, _inner_query(h1, w1, w2)), h1++; if (h2 & 1) --h2, res = f(res, _inner_query(h2, w1, w2)); } return res; } }; /** * @brief 二次元セグメント木 * @docs docs/data-structure-2d/2d-segment-tree.md */ void solve(){ ll h,w; cin>>h>>w; V s(h+1); rep(i,h){ cin>>s[i]; s[i]+="#"; } rep(i,w+1) s[h]+="#"; SegmentTree2D seg(h+1,w+1,[](int a,int b){return a+b;},0); rep(i,h){ rep(j,w){ if(s[i][j]=='#') continue; bool key=false; if(i==0){ if(s[i+1][j]=='.') key=true; } else{ if(s[i-1][j]=='#'&&s[i+1][j]=='.') key=true; } if(j==0){ if(s[i][j+1]=='.') key=true; } else{ if(s[i][j-1]=='#'&&s[i][j+1]=='.') key=true; } if(key) seg.set(i,j,1); } } seg.build(); ll q; cin>>q; rep(i,q){ ll a,b,c,d; cin>>a>>b>>c>>d; ll ans=seg.query(a,b,c,d); if(s[a-1][b-1]=='.') ans++; rep(i,a,c) if(s[i][b-1]=='.'&&(s[i-1][b-1]=='#'||(s[i][b]=='.'&&b!=d))) ans++; rep(i,b,d) if(s[a-1][i]=='.'&&(s[a-1][i-1]=='#'||(s[a][i]=='.'&&a!=c))) ans++; cout<> t; rep(tt,t){ solve(); } return 0; }