考虑某个格子(a)，假设有一个和(a)相邻的格子(b)，且初始时(a), (b)颜色相同。那么，在接下来的每一轮中，(a), (b)将永远同色，而且会交替闪烁（一轮(0)，一轮(1) ......）。我们称(a)和(b)这样的格子为闪烁的格子。
再考虑一个初始时周围没有同色格子的格子(c)。首先，在第一轮中，(c)的颜色显然不会变。如果(c)和某个闪烁的格子相邻，那么第一轮结束后，这个闪烁的格子会变成(c)的颜色。从此开始，(c)会和闪烁的格子一起闪烁。
考虑一个询问((x,y,p))，求出距离格子((x,y))最近的闪烁的格子（特别地，如果((x,y))本身就是闪烁的格子，则距离为(0)）。设这个最近距离为(d)，那么从第(d)轮开始，((x,y))将会闪烁。因此：
- 如果(p<d)，那么答案就是((x,y))初始时的颜色。
- 否则：
- 当((p-d))为偶数时，答案是((x,y))初始时的颜色；
- 当((p-d))为奇数时，答案是不同于初始时颜色的另一种颜色。
于是问题转化为如何快速求出((x,y))与最近的闪烁点的距离(d)。考虑二分这个距离，转化为check是否有距离((x,y))小于等于(d)的闪烁点。这个距离是曼哈顿距离，(leq d)的点形成一个菱形区域，不太好check。可以转成切比雪夫距离（((x,y) o (x+y,x-y))），此时距离((x,y))小于等于(d)的点形成一个正方形区域。做二维前缀和即可。
时间复杂度(O(nm+Tlog n))。
参考代码：
//problem:CF1349C
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int MAXN=2000;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m,T,f[MAXN+5][MAXN+5],dis[MAXN+5][MAXN+5];
char s[MAXN+5][MAXN+5];
int calc(int x1,int y1,int x2,int y2){
assert(1<=x1&&x1<=n+m);
assert(1<=y1&&y1<=n+m);
assert(1<=x2&&x2<=n+m);
assert(1<=y2&&y2<=n+m);
assert(x1<=x2);
assert(y1<=y2);
return f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1];
}
bool find(int x,int y,int len){
int tx=min(x-1,len);
int ty=min(y-1,len);
if(calc(x-tx,y-ty,x,y))return true;//左上方
ty=min(n+m-y,len);
if(calc(x-tx,y,x,y+ty))return true;//右上方
tx=min(n+m-x,len);
ty=min(y-1,len);
if(calc(x,y-ty,x+tx,y))return true;//左下方
ty=min(n+m-y,len);
if(calc(x,y,x+tx,y+ty))return true;//右下方
return false;
}
int main() {
cin>>n>>m>>T;
for(int i=1;i<=n;++i){
cin>>(s[i]+1);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
dis[i][j]=-1;
bool alldif=true;
for(int k=0;k<4;++k){
int ii=i+dx[k],jj=j+dy[k];
if(ii<1||ii>n||jj<1||jj>m)continue;
if(s[ii][jj]==s[i][j]){
alldif=false;
break;
}
}
if(!alldif){
f[i+j][i-j+m]=1;
}
}
}
for(int i=1;i<=n+m;++i)for(int j=1;j<=n+m;++j)f[i][j]+=f[i][j-1];
for(int i=2;i<=n+m;++i)for(int j=1;j<=n+m;++j)f[i][j]+=f[i-1][j];
while(T--){
int x,y;ll p;
cin>>x>>y>>p;
int d=0;
if(dis[x][y]!=-1){
d=dis[x][y];
}
else{
int l=0,r=MAXN;
while(l<r){
int mid=(l+r)>>1;
if(find(x+y,x-y+m,mid))r=mid;
else l=mid+1;
}
d=dis[x][y]=l;
}
if(d==MAXN||p<d){
cout<<s[x][y]<<endl;
}
else{
if((p-d)%2)cout<<((s[x][y]-'0')^1)<<endl;
else cout<<s[x][y]<<endl;
}
}
return 0;
}