略有一点毒瘤的细节题。

观察到我们每次只能横向打通所有街道，纵向的道路是无法打通的。于是我们对于初始状态的每一个连通块，根据其能到达的最北和最南的路口，将其对应到一个区间 $[l_i,r_i]$ 上。这样问题转变为，给你若干多个目标区间，你可以用 $C_i$ 的时间打通一个点，使所有该点上的区间合并，每次询问将所有目标区间合并的最小时间。

首先考虑 $C=1$ 的单次询问。首先将对询问区间去重，对于有包含关系的区间，可去掉外侧的一个。然后将区间排序，预处理出 $nxt_i$ 表示打通 $i$ 之后，通过 $i$ 处的任意区间能到的最右的坐标。然后设当前打通的位置为 $i$，则每次贪心地找到 $i$ 之后的首个询问区间的右端点 $r_x$，则下一次打通的位置应当为 $\min(nxt_i,r_x)$。对于有多次询问的情况，不难发现打通 $r_x$ 的操作最多执行询问区间数那么多次，于是对于中途连续跳转 $nxt_i$ 的部分（也即 $i$ 不在任意一个询问区间内）用倍增维护即可。

$C=1$ 或 $2$ 的情况，可以在上述贪心做法下扩展。此时由于 $C=2$ 的点存在，我们需要同时维护多个代价。设 $dp_i$ 表示花费代价 $i$，能打通的最靠右的位置。设 $nxtp_i$ 表示打通 $i$ 后，下一次应当打通的位置，也即上一段中的 $\min(nxt_i,r_x)$；设 $pre_i$ 表示 $i$ 及 $i$ 以前的首个 $C=1$ 的位置，则每次有转移 $dp_{i}=\max(nxtp_{dp_{i-2}},pre_{nxtp_{dp_{i-1}}})$，不难发现转移只与前两位有关，可以滚动一下。这个解法同样可以倍增优化。最简单的想法是直接维护 $f_{i,j}$ 表示从打通的 $i$ 开始，花费 $2^j$ 能打通的最右侧的位置，但你会发现形如 $2^{j}-1\to2^j+1$ 的代价变化是无法表示的。这种情况显然只会在代价为 $2^j-1$ 时出现，于是预处理 $f_{i,j,0/1}$ 表示从打通的 $i$ 开始，花费为 $2^j-1$，或 $2^j$ 能打通的最右侧的点。显然有边界 $f_{i,0,0}=i$，$f_{i,0,1}=\max(i,pre_{nxt_i})$，于是有下面两种转移：

• $f_{i,j,0}=\max (f_{f_{i,j-1,0},j-1,1},f_{f_{i,j-1,1},j-1,0})$；
• $f_{i,j,1}=\max (f_{f_{i,j-1,1},j-1,1},f_{nxt_{f_{i,j-1,0},j-1,0}})$。

当 $dp_i$ 和 $dp_{i-1}$ 均不在任意一个询问区间内时，倍增转移即可。倍增的终点是恰好停在某个询问区间之外，再下一步就进入询问区间了（我们希望首次进入询问区间就停下来，做 $r_x$ 的转移）。这样，我们倍增的总次数仍然是 $\sum T_Q$ 级别的。枚举每一次倍增的幂次 $j$，转移式为：

• $dp_{i-1}=\max (f_{dp_{i-2^j},j,0},f_{dp_{i-2^j-1},j,1})$；
• $dp_i=\max(f_{dp_{i-2^j},j,1},f_{nxt_{dp_{i-2^j-1}},j,0})$。

设首个询问区间的右端点为 $r_1$，最后一个询问区间的左端点为 $l_m$，则初始状态为 $dp_0=0$，$dp_1=pre_{r_1}$。当存在一个 $dp$ 值大于等于 $l_m$ 时就找到答案了。不难发现在 $dp$ 转移过程中，有效的位置永远只有 $2$ 个，所以我们可以只维护当前的两个有效位置及其值。注意需要提前判断无解（即 $r_1$ 和 $l_m$ 中间有无线端覆盖的位置）的情况，维护空隙个数的前缀和即可。最后的答案可能在 $dp_{i}$ 或 $dp_{i-1}$ 的位置取到，两边同时判断即可。

实现时细节较多。时间复杂度 $O(\alpha(HW)+\sum T_Q\log H)$。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) x*2
#define rs(x) x*2+1
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define qingbai 666
using namespace std;
const int N=1e6+5,S=(1<<20)+5,mo1=1e9+9,base1=19491001,mo2=998244353,base2=19260817,inf=1e9+7;
typedef long long ll;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int n,m,q;
int c[N],nxt[N],pre[N],f[N][22][2],dp[2],cntl,id[N],emp[N];
pii l[N];
int getp(int x,int y){
	return (x-1)*m+y;
}
struct bcj{
	int fa[N];
	void init(){
		rep(i,1,n*m)
		    fa[i]=i;
	}
	int find(int x){
		if(fa[x]==x)return x;
		return fa[x]=find(fa[x]);
	}
	void merge(int x,int y){
		int fx=find(x),fy=find(y);
		if(fx!=fy)fa[fx]=fy;
	}
}B;
bool cmpl(pii x,pii y){
	if(x.fir==y.fir)return x.sec>y.sec;
	return x.fir<y.fir;
}
void solve(){
	int t;
	read(t);
	vector<int>s;
	vector<pii>nl,ql;
	rep(i,1,t){
		int x,y;
		read(x),read(y),s.push_back(id[B.find(getp(x,y))]);
    }
    sort(s.begin(),s.end()),s.erase(unique(s.begin(),s.end()),s.end());
    if(s.size()==1){
    	puts("0");
    	return;
    }
    for(auto i:s)
	    nl.push_back(l[i]);
	sort(nl.begin(),nl.end(),cmpl);
	for(auto i:nl){
		while(ql.size()&&ql.back().fir<=i.fir&&ql.back().sec>=i.sec)
		    ql.pop_back();
		ql.push_back(i);
	}
	int maxl=0,minr=inf;
	for(auto i:ql)
	    maxl=max(maxl,i.fir),minr=min(minr,i.sec);
	if(emp[maxl]-emp[minr]>0){
		puts("-1");
		return;
	}
	int ans=1;
	dp[0]=0,dp[1]=pre[minr],nxt[0]=minr;
	while(dp[1]<maxl&&dp[0]<maxl){
		int lim1=upper_bound(ql.begin(),ql.end(),mp(dp[1],inf))-ql.begin();	    
		int lim0=upper_bound(ql.begin(),ql.end(),mp(dp[0],inf))-ql.begin();
		repp(i,21,0){
		    //注意倍增过程中一定不能进入询问区间内，因为我们希望首次跳到询问区间就停下来.
			int nwv[2];
			nwv[0]=max(f[dp[1]][i][0],f[dp[0]][i][1]);
			nwv[1]=max(f[dp[1]][i][1],f[nxt[dp[0]]][i][0]);
			if(nwv[1]<ql[lim1].fir&&nwv[0]<ql[lim0].fir)dp[0]=nwv[0],dp[1]=nwv[1],ans+=1<<i; 
		}
	    //倍增结束后做一次单独的dp转移即可 
	    int pre0=dp[0],pre1=dp[1];
		dp[0]=pre1,dp[1]=max(min(nxt[pre0],ql[lim0].sec),pre[min(nxt[pre1],ql[lim1].sec)]),ans++;
	}
	if(dp[0]>=maxl)printf("%d\n",ans-1);
	else printf("%d\n",ans);
	return;
}
int main(){
	read(n),read(m),read(q);
	B.init();
	rep(i,1,n){
		string s;
		cin>>s;
		rep(j,1,m-1)
		    if(s[j-1]-'0'==1)B.merge(getp(i,j),getp(i,j+1));
	}
	rep(i,1,n-1){
		string s;
		cin>>s;
		rep(j,1,m)
		    if(s[j-1]-'0'==1)B.merge(getp(i,j),getp(i+1,j));
	}
	rep(i,1,n){
		read(c[i]);
		if(c[i]==1)pre[i]=i;
		else pre[i]=pre[i-1];
	}
	rep(i,1,n*m)
	    l[i]=mp(inf,0);
	rep(i,1,n){
		rep(j,1,m){
			int nwf=B.find(getp(i,j));
			l[nwf]=mp(min(l[nwf].fir,i),max(l[nwf].sec,i));
		}
	}
	rep(i,1,n*m)
		if(B.fa[i]==i)l[++cntl]=l[i],id[i]=cntl;
	rep(i,1,cntl)
	    nxt[l[i].fir]=max(nxt[l[i].fir],l[i].sec);
	rep(i,1,n)
	    nxt[i]=max(nxt[i],nxt[i-1]),emp[i]=emp[i-1]+(nxt[i-1]<i);
	rep(i,1,n)
	    f[i][0][0]=i,f[i][0][1]=max(i,pre[nxt[i]]);
	rep(j,1,21){
		rep(i,1,n){
			f[i][j][0]=max(f[f[i][j-1][0]][j-1][1],f[f[i][j-1][1]][j-1][0]);
			f[i][j][1]=max(f[f[i][j-1][1]][j-1][1],f[nxt[f[i][j-1][0]]][j-1][0]);
		}
    }
	while(q--)
	    solve();
	return 0;
}