#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int tree_siz = 1024*2048-1;
int drzewo[tree_siz+1];
int get_min(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return 1e9;
if(p1 >= s1 && p2 <= s2) return drzewo[akt];
return min(get_min(akt*2,p1,(p1+p2)/2,s1,s2),get_min(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
void upd(int v)
{
drzewo[v] = min(drzewo[v*2+1],drzewo[v*2]);
if(v != 1) upd(v/2);
}
void change(int ind, int v)
{
drzewo[tree_siz/2+1+ind] = v;
upd((tree_siz/2+ind+1)/2);
}
struct jump_str
{
int j0,j1,j2;
int dist = 0;
};
jump_str jump[2000'005][21];
jump_str merge_jumps(jump_str s1, int P)
{
if(s1.dist == 0) return jump[s1.j0][P];
jump_str ans;
ans.dist = s1.dist + (1 << P);
ans.j0 = max(jump[s1.j0][P].j1,jump[s1.j1][P].j0);
ans.j1 = max(jump[s1.j0][P].j2,jump[s1.j1][P].j1);
ans.j2 = max(jump[s1.j1][P].j2,jump[s1.j2][P].j1);
return ans;
}
int pref[2000'005][3];
vi graph[2000'005];
int comp[2000'005];
int y_index[2000'005];
int cost[2000'005];
vector<pair<pii,int>> seg2;
int real_seg[2000'005];
vector<pii> seg;
bool odw[2000'005];
int m = 1;
int prev_[2000'005][3];
vector<pii> events[2000'005];
int nxt_jump[2000'005];
int down_pref[2000'005];
int best_seg[2000'005];
int r_seg[2000'005];
ll W,H,q;
pii dfs(int v)
{
comp[v] = m;
pii w = {y_index[v],y_index[v]};
forall(it,graph[v])
{
if(comp[it] == -1)
{
pii w2 = dfs(it);
w.ff = min(w.ff,w2.ff);
w.ss = max(w.ss,w2.ss);
}
}
return w;
}
void calc_pointers()
{
set<int> cost1;
set<int> cost2;
multiset<int> multi;
vector<pii> eve;
rep(i,m-1)
{
eve.pb({seg[i].ff,i});
eve.pb({seg[i].ss+1,i+m});
// cout << seg[i].ff << " " << i << " add\n";
// cout << seg[i].ss+1 << " xd\n";
}
sort(all(eve));
int cur_event = 0;
rep2(i,1,H)
{
while(cur_event != siz(eve) && eve[cur_event].ff == i)
{
if(eve[cur_event].ss < m)
{
multi.insert(eve[cur_event].ss);
}
else
{
multi.erase(multi.find(eve[cur_event].ss-m));
}
cur_event++;
}
// cout << i << " " << siz(multi) << " " << cur_event << " " << eve[cur_event].ff<< " siz\n";
auto it = multi.end();
if(it != multi.begin())
{
it--;
best_seg[i] = *it;
}
if(cost[i] == 1) cost1.insert(i);
else cost2.insert(i);
}
// rep2(i,1,H)
// {
// cout << best_seg[i] << " " << seg[best_seg[i]].ff << " " << seg[best_seg[i]].ss << " " << i << " best\n";
// }
rep(i,m-1)
{
//cost 0
jump[i][0].j0 = i;
jump[i][0].j1 = i;
jump[i][0].j2 = i;
jump[i][0].dist = 1;
//cost 1
auto it = cost1.upper_bound(seg[i].ss);
if(it != cost1.begin())
{
it--;
int v = *it;
if(!(v < seg[i].ff))
{
jump[i][0].j1 = best_seg[v];
}
}
//cost 2
it = cost2.upper_bound(seg[i].ss);
if(it != cost2.begin())
{
it--;
int v = *it;
if(!(v < seg[i].ff))
{
jump[i][0].j2 = best_seg[v];
}
}
}
rep(i,m-1)
{
jump[i][0].j2 = max(jump[i][0].j2,jump[jump[i][0].j1][0].j1);
}
rep2(bit,1,20)
{
rep(i,m)
{
jump[i][bit] = merge_jumps(jump[i][bit-1],bit-1);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
cin >> H >> W >> q;
rep(i,tree_siz) drzewo[i+1] = 1e9;
rep(i,H)
{
rep(j,W)
{
int cell = i*W+j;
y_index[cell] = i+1;
comp[cell] = -1;
}
}
rep(i,H)
{
rep(j,W-1)
{
int cell = i*W+j;
char z;
cin >> z;
if(z == '1')
{
graph[cell].pb(cell+1);
graph[cell+1].pb(cell);
}
}
}
rep(i,H-1)
{
rep(j,W)
{
int cell = i*W+j;
char z;
cin >> z;
if(z == '1')
{
down_pref[i+1] = 1;
graph[cell].pb(cell+W);
graph[cell+W].pb(cell);
}
}
}
rep2(i,1,H)
{
down_pref[i] += down_pref[i-1];
}
rep(i,H) cin >> cost[i+1];
rep(i,H)
{
pref[i+1][1] = pref[i][1];
pref[i+1][2] = pref[i][2];
pref[i+1][cost[i+1]]++;
}
rep(i,H*W)
{
if(comp[i] == -1)
{
pii s = dfs(i);
// cout << i << " new\n";
seg2.pb({{s.ss,-s.ff},m});
m++;
}
}
sort(all(seg2));
rep2(i,1,m-1)
{
seg.pb({-seg2[i-1].ff.ss,seg2[i-1].ff.ff});
real_seg[seg2[i-1].ss] = i-1;
}
rep(i,m-1)
{
rep2(j,seg[i].ff,seg[i].ss)
{
r_seg[j] = i;
}
}
rep(i,H*W) comp[i] = real_seg[comp[i]];
prev_[0][1] = -1;
prev_[0][2] = -1;
rep2(i,1,H)
{
prev_[i][1] = prev_[i-1][1];
prev_[i][2] = prev_[i-1][2];
if(cost[i] == 1) prev_[i][1] = i;
if(cost[i] == 2) prev_[i][2] = i;
}
multiset<int> mult;
forall(it,seg)
{
events[it.ss].pb({it.ss,1});
events[it.ff-1].pb({it.ss,-1});
}
for(int i = H; i >= 1; i--)
{
forall(it,events[i])
{
if(it.ss == 1)
{
mult.insert(it.ff);
}
else
{
mult.erase(mult.find(it.ff));
}
}
auto it = mult.end();
it--;
nxt_jump[i] = *it;
}
calc_pointers();
rep(qq,q)
{
int t;
cin >> t;
vector<int> points;
rep(j,t)
{
int y,x;
cin >> y >> x;
y--;
x--;
int cell = y*W + x;
points.pb(comp[cell]);
}
sort(all(points));
vi rest;
int prv = -1;
int cnt = 0;
forall(it,points)
{
if(it == prv) continue;
prv = it;
cnt++;
if(get_min(1,0,tree_siz/2,seg[it].ff,seg[it].ss) > seg[it].ss) rest.pb(it);
change(seg[it].ff,seg[it].ss);
}
forall(it,points)
{
change(seg[it].ff,1e9);
}
if(cnt == 1)
{
cout << "0\n";
continue;
}
// cout << siz(rest) << " rest\n";
if(siz(rest) == 1)
{
if(pref[seg[rest[0]].ss][1] - pref[seg[rest[0]].ff-1][1] > 0)
{
cout << "1\n";
}
else
{
cout << "2\n";
}
continue;
}
// cout << down_pref[seg[rest[siz(rest)-1]].ss-1] << " " << down_pref[seg[rest[0]].ff-1] << " " << rest[0] << " " << rest[siz(rest)-1] << " " << seg[rest[0]].ff << " " << seg[rest[0]].ss << " " << seg[rest[1]].ff << " " << seg[rest[1]].ss << " down\n";
if(down_pref[seg[rest[siz(rest)-1]].ss-1] - down_pref[seg[rest[0]].ff-1] != seg[rest[siz(rest)-1]].ss-seg[rest[0]].ff)
{
cout << "-1\n";
continue;
}
int beg = seg[rest[0]].ff;
pii dp_ans1;
pii dp_ans2;
int cur_ans = 1;
dp_ans1 = {0,seg[rest[0]].ss};
int cut = prev_[seg[rest[0]].ss][1];
// cout << cut << " cut\n";
if(cut < beg)
{
dp_ans2 = {0,seg[rest[0]].ss};
}
else
{
int com_l = seg[rest[0]].ff;
int com_r = seg[rest[0]].ss;
bool was = 0;
rep(i,siz(rest))
{
int new_l = max(com_l,seg[rest[i]].ff);
int new_r = min(com_r,seg[rest[i]].ss);
if(new_l > new_r || cut < new_l || cut > new_r)
{
dp_ans2 = {i-1,nxt_jump[cut]};
was = 1;
break;
}
com_l = new_l;
com_r = new_r;
}
if(!was)
{
cout << "1\n";
continue;
}
}
// cout << dp_ans1.ff << " " << dp_ans1.ss << " dp\n";
// cout << dp_ans2.ff << " " << dp_ans2.ss << " dp2\n";
while(true)
{
if(dp_ans2.ff == siz(rest)-1)
{
cout << cur_ans << "\n";
continue;
}
//cout << cur_ans << " ans\n";
//cout << dp_ans1.ff << " " << dp_ans1.ss << " dp\n";
//cout << dp_ans2.ff << " " << dp_ans2.ss << " dp2\n\n";
cur_ans++;
if(cur_ans > H*2)
{
int a = cur_ans-cur_ans;
int b = cur_ans;
cout << b/a;
}
pii new_dp = {-1,-1};
// ans - 2
if(prev_[dp_ans1.ss][2] >= beg)
{
int v = dp_ans1.ff+1;
int com_l = seg[rest[v]].ff;
int com_r = dp_ans1.ss;
while(com_l <= com_r && v < siz(rest))
{
int new_l = max(com_l,seg[rest[v]].ff);
int new_r = min(com_r,seg[rest[v]].ss);
if(new_l <= new_r && prev_[new_r][2] >= new_l)
{
v++;
com_l = new_l;
com_r = new_r;
}
else
{
break;
}
}
// cout << v << " v\n";
new_dp = max(new_dp,{v-1,nxt_jump[prev_[com_r][2]]});
}
if(prev_[dp_ans2.ss][1] >= beg)
{
int v = dp_ans2.ff+1;
int com_l = seg[rest[v]].ff;
int com_r = dp_ans2.ss;
while(com_l <= com_r && v < siz(rest))
{
int new_l = max(com_l,seg[rest[v]].ff);
int new_r = min(com_r,seg[rest[v]].ss);
if(new_l <= new_r && prev_[new_r][1] >= new_l)
{
v++;
com_l = new_l;
com_r = new_r;
}
else
{
break;
}
}
new_dp = max(new_dp,{v-1,nxt_jump[prev_[com_r][1]]});
}
if(new_dp.ff == siz(rest)-1)
{
cout << cur_ans << "\n";
break;
}
// cout << new_dp.ff << " " << new_dp.ss << " new_dp\n";
ll nak = max(dp_ans1.ss,dp_ans2.ss);
if(new_dp.ff == dp_ans2.ff && dp_ans1.ff == dp_ans2.ff && seg[rest[new_dp.ff+1]].ff > max(nxt_jump[prev_[nak][1]],nxt_jump[prev_[nak][2]]))
{
cur_ans--;
vector<pair<int,pii>> nxt_dp;
int v = rest[new_dp.ff+1];
int v_ind = new_dp.ff+1;
int end_seg = dp_ans1.ss;
//dp_ans1
rep2(k,1,2)
{
if(prev_[end_seg][k] >= beg)
{
int start_seg = r_seg[prev_[end_seg][k]];
jump_str cur_jump = {start_seg,start_seg,start_seg,0};
for(int bit = 20; bit >= 0; bit--)
{
jump_str new_jump = merge_jumps(cur_jump,bit);
if(seg[new_jump.j1].ss < seg[v].ff)
{
cur_jump = new_jump;
}
}
jump_str cur_jump2 = merge_jumps(cur_jump,0);
// cout << jump[3][0].j0 << " " << jump[3][0].j1 << " " << jump[3][0].j2 << " j\n";
// cout << seg[jump[3][0].j1].ff << " " << seg[jump[3][0].j1].ss<< " seg\n";
if(cur_jump2.j1 == v || seg[start_seg].ss >= seg[v].ff)
{
cur_jump2 = cur_jump;
}
// cout << cur_jump2.dist << " " << cur_jump2.j1 << " " << seg[cur_jump2.j1].ff << " " << seg[cur_jump2.j1].ss << " jump\n";
// cout << cur_ans << " " << k << " " << start_seg << " " << seg[start_seg].ff << " " << seg[start_seg].ss << " ans1\n";
nxt_dp.pb({cur_ans-1+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j1].ss}});
nxt_dp.pb({cur_ans-2+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j0].ss}});
}
}
//dp_ans2
end_seg = dp_ans2.ss;
rep2(k,1,2)
{
if(prev_[end_seg][k] >= beg)
{
int start_seg = r_seg[prev_[end_seg][k]];
jump_str cur_jump = {start_seg,start_seg,start_seg,0};
for(int bit = 20; bit >= 0; bit--)
{
jump_str new_jump = merge_jumps(cur_jump,bit);
if(seg[new_jump.j1].ss < seg[v].ff)
{
cur_jump = new_jump;
}
}
jump_str cur_jump2 = merge_jumps(cur_jump,0);
if(cur_jump2.j1 == v || seg[start_seg].ss >= seg[v].ff)
{
cur_jump2 = cur_jump;
}
// cout << cur_jump2.dist << " " << cur_jump2.j1 << " " << seg[cur_jump2.j1].ff << " " << seg[cur_jump2.j1].ss << " jump\n";
// cout << cur_ans << " " << k << " " << start_seg << " " << seg[start_seg].ff << " " << seg[start_seg].ss << " ans1\n";
nxt_dp.pb({cur_ans+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j1].ss}});
nxt_dp.pb({cur_ans-1+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j0].ss}});
}
}
int mini = 1e9;
forall(it,nxt_dp)
{
// cout << it.ff << " " << it.ss.ff << " " << it.ss.ss << " nxt\n";
mini = min(mini,it.ff);
}
// cout << " nxt_dp\n";
cur_ans = mini+1;
dp_ans1 = {-1e9,-1e9};
dp_ans2 = {-1e9,-1e9};
forall(it,nxt_dp)
{
if(it.ff == mini)
{
dp_ans1 = max(dp_ans1,it.ss);
}
else if(it.ff == mini+1)
{
dp_ans2 = max(dp_ans2,it.ss);
}
}
}
else
{
dp_ans1 = dp_ans2;
dp_ans2 = new_dp;
}
}
}
}
