#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : c)
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
constexpr int maxn = 1e6 + 7, maxLog = dbg ? 3 : 23, inf = 1e9 + 8;
int h, w, q, n;
vector<int> graf[maxn];
int component[maxn], top[maxn], bottom[maxn];
int jp[maxn][maxLog];
pair<int, int> jp2[maxn][maxLog]; // { jump 2^j , jump 2^j - 1 }
int rowCosts[maxn];
bool twos;
int cToRow1[maxn], cToRow2[maxn], rowToC[maxn];
int secondRTC[maxn];
int lowestSon1[maxn], lowestSon2[maxn];
vector<vector<int>> xd1, xd2;
bool cmpBottom(int a, int b) {
if(bottom[a] == bottom[b]) return top[a] < top[b];
return bottom[a] < bottom[b];
}
bool cmpTop(int a, int b) {
if(top[a] == top[b]) return bottom[a] < bottom[b];
return top[a] < top[b];
}
void input() {
cin >> h >> w >> q;
char c;
xd1.resize(h, vector<int>(w - 1));
rep(i, 0, h) rep(j, 0, w - 1) cin >> c, (c == '1' ? graf[i * w + j].pb(i * w + j + 1), graf[i * w + j + 1].pb(i * w + j), 0 : 0), xd1[i][j] = c == '1';
xd2.resize(h - 1, vector<int>(w));
rep(i, 0, h - 1) rep(j, 0, w) cin >> c, (c == '1' ? graf[i * w + j].pb(i * w + j + w), graf[i * w + j + w].pb(i * w + j), 0 : 0), xd2[i][j] = c == '1';
rep(i, 0, h) cin >> rowCosts[i], twos = twos || (rowCosts[i] == 2);
}
void dfsComponents(int v, int c) {
component[v] = c;
top[c] = min(top[c], v / w);
bottom[c] = max(bottom[c], v / w);
repIn(u, graf[v]) if (!component[u]) dfsComponents(u, c);
}
void calcComponents() {
top[0] = bottom[0] = -1;
DC << "Components: " << eol;
rep(i, 0, h) rep(j, 0, w) if (!component[i * w + j]) {
n++;
top[n] = bottom[n] = i;
dfsComponents(i * w + j, n);
DC << " comp " << n << " from " << i << ' ' << j << " -> top " << top[n] << " bottom " << bottom[n] << eol;
}
}
void calcLowest() {
rep(i, 1, n + 1) cToRow1[i] = cToRow2[i] = -1;
repD(i, h - 1, -1) {
rep(j, 0, w) {
auto c = component[i * w + j];
if (rowToC[i] == 0 || bottom[c] > bottom[rowToC[i]]) secondRTC[i] = rowToC[i], rowToC[i] = c;
else if (secondRTC[i] == 0 || bottom[c] > bottom[secondRTC[i]]) secondRTC[i] = c;
if (rowCosts[i] == 1) if (cToRow1[c] == -1) cToRow1[c] = i;
if (rowCosts[i] == 2) if (cToRow2[c] == -1) cToRow2[c] = i;
}
}
//return;
DEBUG {
DC << "Component to row: " << eol;
rep(i, 1, n + 1) DC << " " << i << ": 1 -> " << cToRow1[i] << " 2 -> " << cToRow2[i] << eol;
DC << "Row to component: " << eol;
rep(i, 0, h) DC << " " << i << " -> " << rowToC[i] << eol;
}
}
void calcLowestSon() {
rep(i, 1, n + 1) lowestSon1[i] = (cToRow1[i] == -1 || bottom[rowToC[cToRow1[i]]] <= bottom[i] ? 0 : rowToC[cToRow1[i]]), lowestSon2[i] = (cToRow2[i] == -1 || bottom[rowToC[cToRow2[i]]] <= bottom[i] ? 0 : rowToC[cToRow2[i]]);
// return;
DEBUG {
DC << "LowestSons: " << eol;
rep(i, 1, n + 1) DC << " " << i << " ls1 " << lowestSon1[i] << " ls2 " << lowestSon2[i] << eol;
}
}
void calcJP() {
rep(i, 1, n + 1) jp[i][0] = lowestSon1[i];
rep(k, 1, maxLog) rep(i, 1, n + 1) jp[i][k] = jp[jp[i][k - 1]][k - 1];
}
void calcJP2() {
rep(i, 1, n + 1) jp2[i][0] = {lowestSon1[i], i};
rep(i, 1, n + 1) jp2[i][1] = {max(lowestSon1[lowestSon1[i]], lowestSon2[i], cmpBottom), lowestSon1[i]};
rep(k, 2, maxLog) rep(i, 1, n + 1) jp2[i][k] = {max(jp2[jp2[i][k - 1].first][k - 1].first, jp2[lowestSon2[jp2[i][k - 1].second]][k - 1].second, cmpBottom), max(jp2[jp2[i][k - 1].second][k - 1].first, jp2[jp2[i][k - 1].first][k - 1].second, cmpBottom)};
DEBUG {
DC << "JP2: " << eol;
rep(i, 1, n + 1) {
DC << ' ' << i << ": ";
rep(k, 0, maxLog) DC << "{" << jp2[i][k].first << ' ' << jp2[i][k].second << "} ";
DC << eol;
}
}
}
pair<int, int> jump(int v, int u) {
DC << "jump " << v << ' ' << u << eol << ' ';
int ans = 0;
repD(k, maxLog - 1, -1) if (jp[v][k] && bottom[jp[v][k]] < top[u]) {
v = jp[v][k], ans += 1 << k;
DC << v << "(" << (1 << k) << ") ";
}
DC << eol;
return {v, ans};
}
pair<pair<int, int>, int> jump2(int v, int vm1, int u) {
DC << " Jumping2 from " << v << " to " << u << eol;
int there = v, thereM1 = vm1;
int cnt = 0;
repD(k, maxLog - 1, -1) if(jp2[there][k].first && bottom[jp2[there][k].first] < top[u]) {
auto prv = there;
there = max(jp2[there][k].first, jp2[lowestSon2[thereM1]][k].second, cmpBottom);
thereM1 = max(jp2[thereM1][k].first, jp2[prv][k].second, cmpBottom);
cnt += (1 << k);
}
DC << " -> " << there << ' ' << thereM1 << " " << cnt << eol;
return {{there, thereM1}, cnt};
}
int query(vector<int>& V) {
int ans = 0;
ranges::sort(V, cmpBottom);
int last = -1;
int v = V[0];
if(!twos) rep(i, 1, (int)V.size()) {
const auto& u = V[i];
DC << "Jumping from " << v << " to " << u << " ; last = " << last << eol;
if (v == u) DC << " skip" << eol;
if (v == u) continue;
if (last >= top[u] && last <= bottom[u]) DC << " skip" << eol;
if (last >= top[u] && last <= bottom[u]) continue;
if (v == 0) return -1;
if (bottom[v] >= top[u]) {
if (bottom[u] >= bottom[v]) last = (cToRow1[v] >= top[u]) ? cToRow1[v] : cToRow2[v];
else last = (cToRow1[u] >= top[v]) ? cToRow1[u] : cToRow2[u];
v = rowToC[last];
ans += rowCosts[last];
DC << " zachodza" << eol;
continue;
}
auto [vv, cost] = jump(v, u);
v = lowestSon1[vv], ans += cost;
if (top[u] > bottom[v]) return -1;
ans += 2;
if (bottom[u] >= bottom[v]) {
last = bottom[v];
v = lowestSon1[v];
}
else {
last = bottom[u];
v = lowestSon1[u];
}
}
if(twos) {
vector<pair<int, int>> dp;
vector<int> tmp;
rep(i, 0, (int)V.size()) if(((!i || V[i - 1] != V[i]) && (i == (int)V.size() - 1 || V[i + 1] != V[i])) || (i && V[i - 1] == V[i] && (i == (int)V.size() - 1 || V[i + 1] != V[i]))) tmp.pb(V[i]);
swap(tmp, V);
DC << " V: ";
repIn(i, V) DC << i << ' ';
DC << eol;
dp.pb({1, V[0]});
ans = 0;
while(!dp.empty() && dp.back().first != (int)V.size()) {
if((dp.size() > 2 && ((dp.back() == dp[dp.size() - 3] && dp.back() == dp[dp.size() - 2])))) { ans = -1; break; }
pair<int, int> toPb = {-1, -1};
auto [lastVi, lastAll] = dp.back();
DC << " dp[" << ans << "] = {" << lastVi << ' ' << lastAll << "}" << eol;
auto lastV = V[lastVi];
auto topNxtV = top[lastV];
auto botNxtV = bottom[lastV];
auto botAll = bottom[lastAll];
if(topNxtV <= botAll) {
// use lowest available to get as many from V as possible
int myRow = -1;
if(botNxtV <= botAll) myRow = cToRow1[lastV];
else myRow = cToRow1[lastAll];
if(myRow >= 0) {
while(lastVi < (int)V.size() && top[V[lastVi]] <= myRow && bottom[V[lastVi]] >= myRow) lastVi++;
toPb = max(toPb, pair{lastVi, rowToC[myRow]});
}
}
else if(lastAll && dp.size() > 1 && dp.back().first == dp[dp.size() - 2].first) {
lastVi = dp.back().first, lastAll = dp.back().second;
auto nxtV = V[lastVi];
auto [wher, cost] = jump2(lastAll, dp[dp.size() - 2].second, nxtV);
auto [where, whereM1] = wher;
if(cost > 1 && pair{lastVi, whereM1} != dp.back()) {
DC << " --dp[" << ans + cost - 1 << "] = {" << lastVi << ' ' << whereM1 << "}" << eol;
dp.pb({lastVi, whereM1});
}
if(cost > 0) {
DC << " -dp[" << ans + cost - 1 << "] = {" << lastVi << ' ' << whereM1 << "}" << eol;
dp.pb({lastVi, where});
}
ans += cost;
if(cost != 0) continue;
}
// use lowest one to get to lower all
toPb = max(toPb, pair{dp.back().first, lowestSon1[lastAll]});
if(dp.size() == 1) {
dp.pb(toPb);
ans++;
continue;
}
// same but move by two
lastVi = dp[dp.size() - 2].first, lastAll = dp[dp.size() - 2].second;
lastV = V[lastVi];
topNxtV = top[lastV];
botNxtV = bottom[lastV];
botAll = bottom[lastAll];
if(topNxtV <= botAll) {
// use lowest available to get as many from V as possible
int myRow = -1;
if(botNxtV <= botAll) myRow = cToRow2[lastV];
else myRow = cToRow2[lastAll];
if(myRow >= 0) {
while(lastVi < (int)V.size() && top[V[lastVi]] <= myRow && bottom[V[lastVi]] >= myRow) lastVi++;
toPb = max(toPb, pair{lastVi, rowToC[myRow]});
}
}
// use lowest one to get to lower all
toPb = max(toPb, pair{dp[dp.size() - 2].first, lowestSon2[lastAll]});
dp.pb(toPb);
ans++;
}
if(!dp.empty()) DC << " dp[" << dp.size() - 1 << "] = {" << dp.back().first << ' ' << dp.back().second << "}" << eol;
}
return ans;
}
void processQueries() {
int t, a, b;
vector<int> V;
rep(i, 0, q) {
DC << "Query " << i << eol;
cin >> t;
V.resize(t);
rep(j, 0, t) cin >> a >> b, V[j] = component[(a - 1) * w + b - 1];
cout << query(V) << '\n';
}
}
void visualise() {
rep(i, 0, h) {
rep(j, 0, 2 * w) {
if(j % 2 == 0) {
DC << (i && xd2[i - 1][j / 2] ? '|' : '.');
}
else {
DC << (j / 2 < xd1[i].size() && xd1[i][j / 2] ? '_' : ' ');
}
}
DC << "\t\t" << rowCosts[i] << "\t\t";
rep(j, 0, w) {
auto c = component[i * w + j];
DC << c;
if(c / 10) { DC << " "; }
else DC << " ";
}
DC << eol;
}
}
int main() {
input();
twos=true;
calcComponents();
calcLowest();
calcLowestSon();
calcJP();
calcJP2();
DEBUG visualise();
processQueries();
return 0;
}
