#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi pair<int,int>
struct d{
int mi = 1e9;
int ma = 0;
};
vector<d> przedzialy;
const int MAXN = 1e6 + 5;
const int MAXK = 20;
bool comp(const int &i1, const int &i2){
if(przedzialy[i1].ma != przedzialy[i2].ma) return przedzialy[i1].ma < przedzialy[i2].ma;
if(przedzialy[i1].mi != przedzialy[i2].mi) return przedzialy[i1].mi < przedzialy[i2].mi;
return false;
}
bool comp2(const pair<int,int> &p1, const pair<int,int> &p2){
if(p1.first != p2.first){
return p1.first < p2.first;
}
if(p1.second != p2.second){
return p1.second > p2.second;
}
return false;
}
void dfs(int a, int b, int nr, vector<vector<int>> &kolorek, vector<vector<vector<pair<int,int>>>> &graf){
if(kolorek[a][b] != -1) return;
kolorek[a][b] = nr;
przedzialy[nr].mi = min(przedzialy.back().mi, a);
przedzialy[nr].ma = max(przedzialy.back().ma, a);
for(auto u : graf[a][b]){
if(kolorek[u.first][u.second] == -1) dfs(u.first, u.second, nr, kolorek, graf);
}
return;
}
struct trzy{
int w1;
int w2;
int koszt;
};
struct dpk{
int koszt;
int zaliczony;
int reach;
int ostatnia;
};
dpk wiekszy(const dpk &d1, const dpk &d2){
if(d1.koszt != d2.koszt){
cout << " huh\n";
exit(0);
}
if(d1.zaliczony != d2.zaliczony){
return (d1.zaliczony > d2.zaliczony ? d1 : d2);
}
if(d1.reach != d2.reach){
return (d1.reach > d2.reach ? d1 : d2);
}
if(d1.ostatnia != d2.ostatnia){
return (d1.ostatnia > d2.ostatnia ? d1 : d2);
}
return d1;
}
int koszt[MAXN];
pair<int,int> poprzedni[MAXN];
pair<int,int> nastepny[MAXN];
vector<pair<int,int>> segments;
trzy nxt[MAXN][MAXK];
int start, koniec;
int prefsum[MAXN];
int reach[MAXN];
trzy merge(pair<int,int> curr, int i){
//nxt[i][j].w1 = max({nxt[nxt[i][j-1].w1][j-1].w2, nxt[nxt[i][j-1].w2][j-1].w1});
//nxt[i][j].w2 = max({nxt[nxt[i][j-1].w2][j-1].w2, nxt[i][j].w1, nxt[i][j].w2, nxt[reach[nxt[i][j].w1]][j-1].w1});
trzy odp;
odp.w1 = max({nxt[curr.first][i-1].w2, nxt[curr.second][i-1].w1});
odp.w2 = max({nxt[curr.second][i-1].w2, odp.w1, odp.w2, nxt[reach[curr.first]][i-1].w1});
return odp;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> kolorek;
vector<vector<vector<pair<int,int>>>> graf;
kolorek.resize(n + 1);
graf.resize(n + 1);
{
for(int i = 0; i <= n; ++i){
kolorek[i].resize(m + 1);
graf[i].resize(m + 1);
}
for(int i = 0; i <= n; ++i){
for(int j = 0; j <= m; ++j){
kolorek[i][j] = -1;
graf[i][j].clear();
}
}
char x;
string s;
for(int i = 1; i <= n; ++i){
cin >> s;
for(int j = 1; j < m; ++j){
x = s[j-1];
//cout << x << " x\n";
if(x == '1') {
graf[i][j].push_back({i,j+1});
graf[i][j+1].push_back({i,j});
}
}
}
//cout << "#\n";
for(int i = 1; i < n; ++i){
cin >> s;
for(int j = 1; j <= m; ++j){
x = s[j-1];
if(x == '1') {
graf[i][j].push_back({i + 1, j});
graf[i+1][j].push_back({i,j});
}
}
}
int nr = 1;
przedzialy.push_back((d){1000000000, 1000000000});
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(kolorek[i][j] == -1){
przedzialy.push_back((d){i, i});
dfs(i, j, nr, kolorek, graf);
nr++;
}
}
}
int p1 = 0;
int p2 = 0;
for(int i = 1; i <= n; ++i){
cin >> koszt[i];
if(koszt[i] == 1){
p1 = i;
}
else{
p2 = i;
}
poprzedni[i] = {p1, p2};
//cout << i << " " << poprzedni[i].first << " " << poprzedni[i].second << " poprzednie\n";
}
p1 = n;
p2 = n;
for(int i = n; i > 0; --i){
if(koszt[i] == 1){
p1 = i;
}
else{
p2 = i;
}
nastepny[i] = {p1, p2};
}
vector<int> ind;
for(int i = 1; i < przedzialy.size(); ++i){
ind.push_back(i);
}
sort(ind.begin(),ind.end(),comp);
vector<d> nowy;
vector<int> nowyind;
nowyind.resize(przedzialy.size());
nowy.resize(przedzialy.size());
for(int i = 1; i < przedzialy.size(); ++i){
nowy[i] = przedzialy[ind[i-1]];
nowyind[ind[i-1]] = i;
}
nowy[0] = przedzialy[0];
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
kolorek[i][j] = nowyind[kolorek[i][j]];
}
}
przedzialy = nowy;
nowyind.clear();
nowy.clear();
prefsum[0] = 0;
for(int i = 1; i <= n; ++i){
reach[i] = i;
for(int j = 1; j <= m; ++j){
reach[i] = max(reach[i], przedzialy[kolorek[i][j]].ma);
}
if(reach[i] == i){
prefsum[i]++;
}
prefsum[i] += prefsum[i-1];
}
}
for(int i = 1; i <= n; ++i){
nxt[i][0] = {i, max(i, poprzedni[reach[i]].first)};
}
for(int j = 1; j <= 19; ++j){
for(int i = 1; i <= n; ++i){
nxt[i][j].w1 = max({nxt[nxt[i][j-1].w1][j-1].w2, nxt[nxt[i][j-1].w2][j-1].w1});
nxt[i][j].w2 = max({nxt[nxt[i][j-1].w2][j-1].w2, nxt[i][j].w1, nxt[reach[nxt[i][j-1].w1]][j-1].w1});
}
}
int r;
int a, b;
for(int i = 0; i < q; ++i){
cin >> r;
set<int> pkt;
segments.clear();
while(r--){
cin >> a >> b;
pkt.insert(kolorek[a][b]);
}
if(pkt.size() == 1){
cout << 0 << "\n";
continue;
}
start = n;
koniec = 0;
for(auto u : pkt){
segments.push_back({przedzialy[u].mi, przedzialy[u].ma});
start = min(start, przedzialy[u].ma);
koniec = max(koniec, przedzialy[u].mi);
}
//cout << start << " " << koniec << " sk\n";
if(prefsum[koniec - 1] - prefsum[start - 1] > 0){
cout << -1 << "\n";
continue;
}
sort(segments.begin(),segments.end(),comp2);
vector<pair<int,int>> dous;
for(auto u : segments){
while(dous.size() > 0 and dous.back().second >= u.second){
dous.pop_back();
}
dous.push_back(u);
}
bool czy = false;
segments = dous;
// for(auto u : segments){
// cout << u.first << " " << u.second << " seg\n";
// }
if(pkt.size() > 1 and segments.size() == 1){
if(poprzedni[segments[0].second].first >= segments[0].first) cout << 1 << "\n";
else cout << 2 << "\n";
continue;
}
dpk prev2 = {0, 0, segments[0].second, -1};
int gdzie = poprzedni[segments[0].second].first;
int ile = 0;
int rc;
int ost;
//cout << gdzie << " gdz\n";
if(gdzie >= segments[0].first){
rc = reach[gdzie];
ost = gdzie;
}
else{
rc = segments[0].second;
ost = -1;
}
pair<int,int> przedz = segments[0];
for(int i = 1; i < segments.size(); ++i){
if(segments[i].first > przedz.second) break;
pair<int,int> teoretyczny = {segments[i].first, przedz.second};
if(poprzedni[teoretyczny.second].first >= teoretyczny.first){
ile = i;
rc = reach[poprzedni[teoretyczny.second].first];
ost = poprzedni[teoretyczny.second].first;
przedz = teoretyczny;
}
else{
break;
}
if(i == segments.size() - 1){
cout << 1 << "\n";
czy = true;
continue;
}
}
dpk prev1 = {1, ile, rc, ost};
//cout << prev2.koszt << " " << prev2.zaliczony << " " << prev2.reach << " prev2\n";
//cout << prev1.koszt << " " << prev1.zaliczony << " " << prev1.reach << " prev1\n";
auto merge = [&](trzy curr, int i){
//cout << curr.w1 << " " << curr.w2 << " " << i << " przed\n";
trzy odp;
odp.koszt = 0;
odp.w1 = max({nxt[curr.w1][i].w2, nxt[curr.w2][i].w1});
//cout << nxt[curr.w2][i].w2 << " " << odp.w1 << " " << reach[curr.w1] << " " << nxt[reach[curr.w1]][i].w1 << " mozliw\n";
odp.w2 = max({nxt[curr.w2][i].w2, odp.w1, nxt[reach[curr.w1]][i].w1});
//cout << odp.w1 << " " << odp.w2 << " po\n";
return odp;
};
int czymozna = true;
while(czy == false and prev1.zaliczony < segments.size()-1 and prev2.zaliczony < segments.size()-1){
//cout << "#\n";
//cout << prev2.koszt << " " << prev2.zaliczony << " " << prev2.reach << " " << prev2.ostatnia << " prev2\n";
//cout << prev1.koszt << " " << prev1.zaliczony << " " << prev1.reach << " " << prev1.ostatnia << " prev1\n";
if(czymozna == true and segments[prev1.zaliczony + 1].first > prev1.reach and segments[prev2.zaliczony + 1].first > prev2.reach and prev1.ostatnia != -1 and prev2.ostatnia != -1){
//cout << "#\n";
int granica = min({koniec, segments[prev1.zaliczony + 1].first, segments[prev2.zaliczony + 1].first});
trzy curr = {prev2.ostatnia, prev1.ostatnia, 0};
for(int i = 19; i >= 1; --i){
trzy tmp = merge(curr, i);
if(reach[tmp.w1] < granica and reach[tmp.w2] < granica){
prev2.koszt += (1 << i);
prev1.koszt += (1 << i);
curr = tmp;
}
}
//cout << curr.w1 << " " << curr.w2 << " po jmp\n";
prev2.ostatnia = curr.w1;
prev2.reach = reach[curr.w1];
prev1.ostatnia = curr.w2;
prev1.reach = reach[curr.w2];
czymozna = false;
continue;
}
dpk moz1;
dpk moz2;
pair<int,int> przedz = {start, prev2.reach};
//cout << przedz.first << " " << przedz.second << " przedzial\n";
int ile = prev2.zaliczony;
int rc = max(reach[poprzedni[prev2.reach].second], prev2.reach);
int ost = max(prev2.ostatnia, poprzedni[prev2.reach].second);
for(int i = ile + 1; i < segments.size(); ++i){
//cout << segments[i].first << " pocz\n";
if(segments[i].first > przedz.second) break;
pair<int,int> teoretyczny = {segments[i].first, min(przedz.second,segments[i].second)};
if(poprzedni[teoretyczny.second].second >= teoretyczny.first){
ile = i;
czymozna = true;
rc = reach[poprzedni[teoretyczny.second].second];
przedz = teoretyczny;
ost = poprzedni[teoretyczny.second].second;
}
else{
break;
}
if(i == segments.size() - 1){
cout << prev2.koszt + 2 << "\n";
czy = true;
continue;
}
}
if(czy == true) break;
moz1 = {prev2.koszt + 2, ile, rc, ost};
ile = prev1.zaliczony;
rc = max(prev1.reach, reach[poprzedni[prev1.reach].first]);
przedz = {start, prev1.reach};
//cout << prev1.reach << " rea1\n";
//cout << poprzedni[prev1.reach].first << " pop1\n";
//cout << przedz.first << " " << przedz.second << " przedzial1\n";
ost = max(prev1.ostatnia, poprzedni[prev1.reach].first);
for(int i = ile + 1; i < segments.size(); ++i){
//cout << segments[i].first << " seg pocz\n";
if(segments[i].first > przedz.second) break;
pair<int,int> teoretyczny = {segments[i].first, min(przedz.second,segments[i].second)};
//cout << teoretyczny.first << " " << teoretyczny.second << " teoretyczny\n";
if(poprzedni[teoretyczny.second].first >= teoretyczny.first){
ile = i;
czymozna = true;
rc = reach[poprzedni[teoretyczny.second].first];
przedz = teoretyczny;
ost = poprzedni[teoretyczny.second].first;
}
else{
break;
}
if(i == segments.size() - 1){
cout << prev1.koszt + 1 << "\n";
czy = true;
continue;
}
}
if(czy == true){
break;
}
moz2 = {prev1.koszt + 1, ile, rc, ost};
//cout << moz1.koszt << " " << moz1.zaliczony << " " << moz1.ostatnia << " " << moz1.reach << " moz1\n";
//cout << moz2.koszt << " " << moz2.zaliczony << " " << moz2.ostatnia << " " << moz2.reach << " moz2\n";
dpk nowy = wiekszy(moz1, moz2);
prev2 = prev1;
prev1 = nowy;
}
if(czy == true) continue;
if(prev2.zaliczony == segments.size()-1){
cout << prev2.koszt << "\n";
continue;
}
cout << prev1.koszt << "\n";
}
return 0;
}
