#include using namespace std; //だるすぎ. int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int H,W,sx,sy; cin >> H >> W >> sx >> sy,sx--,sy--; vector S(H); for(auto &s : S) cin >> s; int N = H*W; vector>> Graph(N+N); int n = Graph.size(); { vector> D1(H); for(int i=0; i= siz){ int left = k+k-siz,right = k+k-siz+1; if(left < W) Graph.at(n+k).push_back({i*W+left,0}); if(right < W) Graph.at(n+k).push_back({i*W+right,0}); } else{ int left = k+k,right = k+k+1; Graph.at(n+k).push_back({n+left,0}); Graph.at(n+k).push_back({n+right,0}); } } n += siz; for(int k=1; k= siz){ int left = k+k-siz,right = k+k-siz+1; if(left < W) Graph.at(n+k).push_back({i*W+left+N,0}); if(right < W) Graph.at(n+k).push_back({i*W+right+N,0}); } else{ int left = k+k,right = k+k+1; Graph.at(n+k).push_back({n+left,0}); Graph.at(n+k).push_back({n+right,0}); } } n += siz; } vector> To(H,vector(W)); for(int i=0; i= siz){ int to = i*W+l-siz; Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = i*W+r-siz; Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } for(int k=W; k--;) if(S.at(i).at(k) != '#'){ int pos = i*W+k; To.at(i).at(k) = k; if(k < W-1 && S.at(i).at(k+1) != '#') To.at(i).at(k) = To.at(i).at(k+1); int l = k+1,r = To.at(i).at(k)+1; l += siz,r += siz; while(l < r){ if(l&1){ if(l >= siz){ int to = i*W+l-siz; Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = i*W+r-siz; Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } } } { vector> D2(W); for(int k=0; k= siz){ int left = i+i-siz,right = left+1; if(left < H) Graph.at(n+i).push_back({left*W+k,0}); if(right < W) Graph.at(n+i).push_back({right*W+k,0}); } else{ int left = i+i,right = i+i+1; Graph.at(n+i).push_back({n+left,0}); Graph.at(n+i).push_back({n+right,0}); } } n += siz; for(int i=1; i= siz){ int left = i+i-siz,right = left+1; if(left < H) Graph.at(n+i).push_back({left*W+k+N,0}); if(right < W) Graph.at(n+i).push_back({right*W+k+N,0}); } else{ int left = i+i,right = i+i+1; Graph.at(n+i).push_back({n+left,0}); Graph.at(n+i).push_back({n+right,0}); } } } vector> To(H,vector(W)); for(int k=0; k= siz){ int to = (l-siz)*W+k; Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = (r-siz)*W+k; Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } for(int i=H; i--;) if(S.at(i).at(k) != '#'){ int pos = i*W+k; To.at(i).at(k) = i; if(i < H-1 && S.at(i+1).at(k) != '#') To.at(i).at(k) = To.at(i+1).at(k); int l = i+1,r = To.at(i).at(k)+1; l += siz,r += siz; while(l < r){ if(l&1){ if(l >= siz){ int to = (l-siz)*W+k; Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = (r-siz)*W+k; Graph.at(pos).push_back({N+to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } } } { vector> D3(H+W); for(int p=0; p= siz){ int left = k+k-siz,right = k+k-siz+1; if(x+left < H && y+left < W) Graph.at(n+k).push_back({(x+left)*W+(y+left),0}); if(x+right < H && y+right < W) Graph.at(n+k).push_back({(x+right)*W+(y+right),0}); } else{ int left = k+k,right = k+k+1; Graph.at(n+k).push_back({n+left,0}); Graph.at(n+k).push_back({n+right,0}); } } n += siz; for(int k=1; k= siz){ int left = k+k-siz,right = k+k-siz+1; if(x+left < H && y+left < W) Graph.at(n+k).push_back({(x+left)*W+(y+left)+N,0}); if(x+right < H && y+right < W) Graph.at(n+k).push_back({(x+right)*W+(y+right)+N,0}); } else{ int left = k+k,right = k+k+1; Graph.at(n+k).push_back({n+left,0}); Graph.at(n+k).push_back({n+right,0}); } } n += siz; } vector> To(H,vector(W)); for(int i=0; i= k) tie(siz,p) = D3.at(i-k); else tie(siz,p) = D3.at(k-i+H-1); if(siz == 1) continue; int pos = i*W+k; To.at(i).at(k) = k; if(i && k && S.at(i-1).at(k-1) != '#') To.at(i).at(k) = To.at(i-1).at(k-1); int lx = To.at(i).at(k)-(k-i),ly = To.at(i).at(k); int Lx = lx-min(lx,ly),Ly = ly-min(lx,ly); int l = min(lx,ly),r = min(i,k); l += siz,r += siz; while(l < r){ if(l&1){ if(l >= siz){ int to = (Lx+l-siz)*W+(Ly+l-siz); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = (Lx+r-siz)*W+(Ly+r-siz); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } } for(int i=H-1; i>=0; i--){ for(int k=0; k= k) tie(siz,p) = D3.at(i-k); else tie(siz,p) = D3.at(k-i+H-1); if(siz == 1) continue; int pos = i*W+k; To.at(i).at(k) = k; if(i < H-1 && k < W-1 && S.at(i+1).at(k+1) != '#') To.at(i).at(k) = To.at(i+1).at(k+1); int rx = To.at(i).at(k)-(k-i),ry = To.at(i).at(k); int Lx = rx-min(rx,ry),Ly = ry-min(rx,ry); int l = min(i,k)+1,r = min(rx,ry)+1; l += siz,r += siz; while(l < r){ if(l&1){ if(l >= siz){ int to = (Lx+l-siz)*W+(Ly+l-siz); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = (Lx+r-siz)*W+(Ly+r-siz); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } } } { vector> D4(H+W); for(int p=0; p= siz){ int left = k+k-siz,right = k+k-siz+1; if(x+left < H && y-left >= 0) Graph.at(n+k).push_back({(x+left)*W+(y-left),0}); if(x+right < H && y-right >= 0) Graph.at(n+k).push_back({(x+right)*W+(y-right),0}); } else{ int left = k+k,right = k+k+1; Graph.at(n+k).push_back({n+left,0}); Graph.at(n+k).push_back({n+right,0}); } } n += siz; for(int k=1; k= siz){ int left = k+k-siz,right = k+k-siz+1; if(x+left < H && y-left >= 0) Graph.at(n+k).push_back({(x+left)*W+(y-left)+N,0}); if(x+right < H && y-right >= 0) Graph.at(n+k).push_back({(x+right)*W+(y-right)+N,0}); } else{ int left = k+k,right = k+k+1; Graph.at(n+k).push_back({n+left,0}); Graph.at(n+k).push_back({n+right,0}); } } n += siz; } vector> To(H,vector(W)); for(int i=0; i= W) Lx += Ly-W+1,Ly = W-1; int l = lx-Lx,r = i-Lx; l += siz,r += siz; while(l < r){ if(l&1){ if(l >= siz){ int to = (Lx+l-siz)*W+(Ly-(l-siz)); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = (Lx+r-siz)*W+(Ly-(r-siz)); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } } for(int i=H-1; i>=0; i--){ for(int k=0; k= W) Lx += Ly-W+1,Ly = W-1; int l = i-Lx+1,r = rx-Lx+1; l += siz,r += siz; while(l < r){ if(l&1){ if(l >= siz){ int to = (Lx+l-siz)*W+(Ly-(l-siz)); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+l,1}),Graph.at(N+pos).push_back({p+l,1}); l++; } if(r&1){ r--; if(r >= siz){ int to = (Lx+r-siz)*W+(Ly-(r-siz)); Graph.at(pos).push_back({N+to,1}); Graph.at(N+pos).push_back({to,1}); } else Graph.at(pos).push_back({p+siz+r,1}),Graph.at(N+pos).push_back({p+r,1}); } l >>= 1,r >>= 1; } } } } int ok = 0; vector dist(n,1001001001); dist.at(sx*W+sy) = 0; deque Q; Q.push_back({sx*W+sy}); while(Q.size()){ auto pos = Q.front(); Q.pop_front(); ok++; int d = dist.at(pos); for(auto [to,w] : Graph.at(pos)){ int v = d+w; if(w == 1){ if(dist.at(to) > v) dist.at(to) = v,Q.push_back(to); } else if(dist.at(to) > v) dist.at(to) = v,Q.push_front(to); } } int q; cin >> q; if(ok == 1){ while(q--) cout << "No\n"; return 0; } while(q--){ int gx,gy,t; cin >> gx >> gy >> t,gx--,gy--; int pos = gx*W+gy; if(t%2) pos += N; int now = dist.at(pos); if(now <= t) cout << "Yes\n"; else cout << "No\n"; } }