#include #define ull unsigned ll #define ll long long #define ld long double #define INFL (ll)3e18 #define INF (int)2e9 #define MOD (ll)998244353 #define MODO (ll)(1e9+7) using namespace std; templateistream&operator>>(istream&is,vector&v); templateistream&operator>>(istream&is,tuple& t); templateistream&operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} templateistream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} templateistream& operator>>(istream& is, tuple& t) {apply([&](auto&... args) {((is >> args), ...);},t);return is;} int main(void){ ios::sync_with_stdio(false); cin.tie(nullptr); int h,w; cin >> h >> w; pair s; cin >> s; vector g(h); cin >> g; vector dst1(h*w,INFL),dst2(h*w,INFL); vector>> to(h*w); vector> rle; for(int i = 0;i < h;i++){ int st = 0; for(int j = 0;j < w;j++){ if(g[i][j] == '#'){ if(st < j-1){ //cout << i << "," << st << " " << i << "," << j << endl; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < j;st++){ to[be].emplace_back(i*w+st,0); to[i*w+st].emplace_back(be,1); } } st = j+1; } } if(st < w-1){ //cout << i << "," << st << " " << i << "," << w << endl; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < w;st++){ to[be].emplace_back(i*w+st,0); to[i*w+st].emplace_back(be,1); } } } for(int j = 0;j < w;j++){ int st = 0; for(int i = 0;i < h;i++){ if(g[i][j] == '#'){ if(st < i-1){ //cout << st << "," << j << " " << i << "," << j << endl; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < i;st++){ to[be].emplace_back(st*w+j,0); to[st*w+j].emplace_back(be,1); } } st = i+1; } } if(st < h-1){ //cout << st << "," << j << " " << h << "," << j << endl; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < h;st++){ to[be].emplace_back(st*w+j,0); to[st*w+j].emplace_back(be,1); } } } for(int i = 0;i < h+w;i++){ int st = 0; for(int j = 0;j < h;j++){ int x = j,y = i-j; if(y >= w){ st = j+1; continue; } else if(y < 0) break; if(g[x][y] == '#'){ if(st < x-1){ //cout << st << "," << i-st << " " << x << "," << y << endl; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < x;st++){ to[be].emplace_back(st*w+i-st,0); to[st*w+i-st].emplace_back(be,1); } } st = j+1; } } if(st < h-1 && i-st >= 0 && i-st < w){ //cout << st << "," << i-st << " " << h << "," << i-h << endl; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < h && i-st < w && i-st >= 0;st++){ to[be].emplace_back(st*w+i-st,0); to[st*w+i-st].emplace_back(be,1); } } } for(int i = 0;i < h+w;i++){ int st = 0; for(int j = 0;j < h;j++){ int x = j,y = x+w-i; if(y < 0){ st = j+1; continue; } else if(y >= w) break; if(g[x][y] == '#'){ if(st < x-1){ //cout << st << "," << st+w-i << " " << x << "," << y << endl; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < x;st++){ to[be].emplace_back(st*w+st+w-i,0); to[st*w+st+w-i].emplace_back(be,1); } } st = j+1; } } if(st < h-1 && st+w-i >= 0 && st+w-i < w){ //cout << st << "," << st+w-i << " "; dst1.push_back(INFL); dst2.push_back(INFL); to.push_back(vector>()); int be = to.size()-1; for(;st < h && st+w-i >= 0 && st+w-i < w;st++){ to[be].emplace_back(st*w+st+w-i,0); to[st*w+st+w-i].emplace_back(be,1); } //cout << st << "," << st+w-i << endl; } } int dx[] = {1,1,1,0,0,-1,-1,-1},dy[] = {1,0,-1,1,-1,1,0,-1}; for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ if(g[i][j] == '#') continue; for(int k = 0;k < 8;k++){ int tx = i+dx[k],ty = j+dy[k]; if(tx < 0 || tx >= h || ty < 0 || ty >= w) continue; if(g[tx][ty] == '#') continue; to[i*w+j].emplace_back(tx*w+ty,1); } } } s.first--,s.second--; deque d; ll S = s.first*w+s.second; d.push_back(S); dst1[S] = 0; while(!d.empty()){ auto t = d.front(); d.pop_front(); for(auto& [i,j]:to[t]){ if(j == 0){ bool f = false; if(dst1[i] > dst1[t]){ dst1[i] = dst1[t]; f = true; } if(dst2[i] > dst2[t]){ dst2[i] = dst2[t]; f = true; } if(f) d.push_front(i); } else{ bool f = false; if(dst1[i] > dst2[t]+2){ dst1[i] = dst2[t]+1; f = true; } if(dst2[i] > dst1[t]+2){ dst2[i] = dst1[t]+1; f = true; } if(f) d.push_back(i); } } } int q; cin >> q; pair go; int t; for(int i = 0;i < q;i++){ cin >> go >> t; go.first--,go.second--; if(s == go){ bool f = false; for(int k = 0;k < 8;k++){ int tx = s.first+dx[k],ty = s.second+dy[k]; if(tx < 0 || tx >= h || ty < 0 || ty >= w) continue; if(g[tx][ty] == '#') continue; f = true; } if((f&&(t%2==0)) || t == 0) cout << "Yes" << endl; else cout << "No" << endl; continue; } ll G = go.first*w+go.second; if(t%2){ if(dst2[G] <= t) cout << "Yes" << endl; else cout << "No" << endl; } else{ if(dst1[G] <= t) cout << "Yes" << endl; else cout << "No" << endl; } } /* for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ if(dst1[i*w+j] == INFL) cout << -1 << ","; else cout << dst1[i*w+j] << ","; if(dst2[i*w+j] == INFL) cout << -1 << " "; else cout << dst2[i*w+j] << " "; } cout << endl; } for(int i = h*w;i < to.size();i++){ if(dst1[i] == INFL) cout << -1 << ","; else cout << dst1[i] << ","; if(dst2[i] == INFL) cout << -1 << " "; else cout << dst2[i] << " "; } cout << endl; //*/ }