稍微有点难

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
#define x first
#define y second
#define pii pair<int,int>
int n, m, q, idlim;

int idh(int x, int y) {
return x * (m + 2) + y;
}

pii hdi(int id) {
return pii(id / (m + 2), id % (m + 2));
}

int idv(int x, int y) {
return y * (n + 2) + x;
}

pii vdi(int id) {
return pii(id % (n + 2), id / (n + 2));
}
template<class T>

struct array2d {
T a[N];
int n, m;
void init(int val = 0) {
memset(a, val, sizeof(a));
}
void set_size(int n, int m, int val = 0) {
this->n = n;
this->m = m;
init(val);
}
T *operator[](int i) {
return a + i * (m + 2);
}
const T *operator[](int i)const {
return a + i * (m + 2);
}
T &operator[](pii p) {
return a[p.x * (m + 2) + p.y];
}
const T &operator[](pii p)const {
return a[p.x * (m + 2) + p.y];
}
};
array2d<int> v, h, col, lv, tim;
vector<pii> piece;

struct node {
int ch[2], sz;
};
node t[N * 30];
int cnt;

void pushup(int x) {
t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz;
}

void insert(int p, int &x, int l, int r) {
if (!x)
x = ++cnt;
if (l == r) {
t[x].sz = 1;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
insert(p, t[x].ch[0], l, mid);
else
insert(p, t[x].ch[1], mid + 1, r);
pushup(x);
}

void erase(int p, int &x, int l, int r) {
if (!x)
return;
if (l == r) {
t[x].sz = 0;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
erase(p, t[x].ch[0], l, mid);
else
erase(p, t[x].ch[1], mid + 1, r);
pushup(x);
}

int merge(int x, int y) {
if (!(x && y))
return x + y;
t[x].ch[0] = merge(t[x].ch[0], t[y].ch[0]);
t[x].ch[1] = merge(t[x].ch[1], t[y].ch[1]);
if (t[x].ch[0] || t[x].ch[1])
pushup(x);
else
t[x].sz |= t[y].sz;
return x;
}

int query_rk(int v, int x, int l, int r) {
if (!t[x].sz)
return 0;
if (l == r)
return t[x].sz;
int mid = (l + r) >> 1;
if (v <= mid)
return query_rk(v, t[x].ch[0], l, mid);
else
return t[t[x].ch[0]].sz + query_rk(v, t[x].ch[1], mid + 1, r);
}

bool exist(int v, int x, int l, int r) {
if (!t[x].sz)
return 0;
if (l == r)
return 1;
int mid = (l + r) >> 1;
if (v <= mid)
return exist(v, t[x].ch[0], l, mid);
else
return exist(v, t[x].ch[1], mid + 1, r);
}

struct DSU_with_lr {
int l[N], r[N], f[N];
int _(int x) {
return f[x] == x ? x : f[x] = _(f[x]);
}
void merge(int x, int y) {
x = (x), y = (y);
if (x == y)
return;
f[x] = y;
l[y] = min(l[y], l[x]);
r[y] = max(r[y], r[x]);
}
int getl(int id) {
return l[(id)];
}
int getr(int id) {
return r[(id)];
}
bool check(int x, int y) {
return _(x) == _(y);
}
};
DSU_with_lr hseg, vseg;

struct block {
int rt0, rt1, rth, rtv;
void merge(block &y) {
rt0 =::merge(rt0, y.rt0);
rt1 =::merge(rt1, y.rt1);
rth =::merge(rth, y.rth);
rtv =::merge(rtv, y.rtv);
}
int get0(int v) {
return query_rk(v, rt0, 1, q);
}
void ins0(int v) {
insert(v, rt0, 1, q);
}
void era0(int v) {
erase(v, rt0, 1, q);
}
int get1(int v) {
return query_rk(v, rt1, 1, q);
}
void ins1(int v) {
insert(v, rt1, 1, q);
}
void era1(int v) {
erase(v, rt1, 1, q);
}
void ins01(int col, int v) {
col ? ins1(v) : ins0(v);
}
void era01(int col, int v) {
col ? era1(v) : era0(v);
}
void insp(int x, int y) {
insert(idh(x, y), rth, 1, idlim);
insert(idv(x, y), rtv, 1, idlim);
}
int getsz(int col, int lv) {
return t[rth].sz + (1 - col ? get1(lv) : get0(lv));
}
int geth(int x, int y1, int y2, int colx, int lvx) {
auto check = [&](int p, int q) {
return col[p][q] == 1 - colx && lv[p][q] <= lvx && exist(lv[p][q], 1 - colx ? rt1 : rt0, 1, ::q);
};
return query_rk(idh(x, y2), rth, 1, idlim) - query_rk(idh(x, y1 - 1), rth, 1, idlim)
+ (h[x][y1 - 1] == 2 && check(x, y1 - 1)) + (h[x][y2] == 2 && check(x, y2 + 1));
}
int getv(int x1, int x2, int y, int colx, int lvx) {
auto check = [&](int p, int q) {
return col[p][q] == 1 - colx && lv[p][q] <= lvx && exist(lv[p][q], 1 - colx ? rt1 : rt0, 1, ::q);
};
return query_rk(idv(x2, y), rtv, 1, idlim) - query_rk(idv(x1 - 1, y), rtv, 1, idlim)
+ (v[x1 - 1][y] == 2 && check(x1 - 1, y)) + (v[x2][y] == 2 && check(x2 + 1, y));
}
};
template<class T>

struct DSU_array2d {
array2d<T>a;
array2d<pii>f;
void init(int val = 0) {
a.init(val);
}
void set_size(int n, int m, int val = 0) {
a.set_size(n, m, val);
f.set_size(n, m, val);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = {i, j};
}
pii _(pii x) {
return x == f[x] ? x : f[x] = (f[x]);
}
T &operator[](pii p) {
return a[(p)];
}
void merge(pii x, pii y) {
x = _(x), y = _(y);
if (x == y)
return;
a[x].merge(a[y]);
f[y] = x;
}
};
DSU_array2d<block> b;

int qsum = 0;
int ans[N];
int lvcnt[N];
void mian() {
cin >> n >> m >> q;
v.set_size(n, m);
h.set_size(n, m);
col.set_size(n, m, -1);
lv.set_size(n, m);
tim.set_size(n, m);
piece.clear();
memset(t, 0, sizeof(t));
memset(&hseg, 0, sizeof(hseg));
memset(&vseg, 0, sizeof(vseg));
memset(lvcnt, 0, sizeof(lvcnt));
b.set_size(n, m);
for (int i = 0; i < N; i++)
hseg.l[i] = hseg.r[i] = hseg.f[i] = i;
for (int i = 0; i < N; i++)
vseg.l[i] = vseg.r[i] = vseg.f[i] = i;
idlim = (n + 3) * (m + 3);

cnt = 1;
for (int i = 1; i <= n; i++)
	for (int j = 1; j < m; j++) {
		char c;
		cin >> c;
		h[i][j] = c - '0';
	}
for (int i = 1; i < n; i++)
	for (int j = 1; j <= m; j++) {
		char c;
		cin >> c;
		v[i][j] = c - '0';
	}
for (int i = 1; i <= q; i++) {
	int colx, lvx, x, y;
	cin >> colx >> lvx >> x >> y;
	col[x][y] = colx;
	lv[x][y] = lvx;
	++lvcnt[lvx];
	tim[x][y] = i;
	piece.push_back(pii(x, y));
}
for (int i = 1; i <= q; i++)
	lvcnt[i] += lvcnt[i - 1];
for (int i = q - 1; i >= 0; --i)
	lv[piece[i].x][piece[i].y] = lvcnt[lv[piece[i].x][piece[i].y]]--;
for (int i = 1; i <= n; i++) {
	for (int j = 1; j < m; j++) {
		if (h[i][j] == 2 && !lv[i][j] && !lv[i][j + 1])
			hseg.merge(idh(i, j), idh(i, j + 1));
		if (h[i][j] == 3 && !lv[i][j] && !lv[i][j + 1])
			b.merge({i, j}, {i, j + 1});
		if (h[i][j] == 3 && lv[i][j] && !lv[i][j + 1]) {
			b[ {i, j + 1}].ins01(col[i][j], lv[i][j]);
		}
		if (h[i][j] == 3 && !lv[i][j] && lv[i][j + 1]) {
			b[ {i, j}].ins01(col[i][j + 1], lv[i][j + 1]);
		}
	}
}
for (int i = 1; i < n; i++) {
	for (int j = 1; j <= m; j++) {
		if (v[i][j] == 2 && !lv[i][j] && !lv[i + 1][j])
			vseg.merge(idv(i, j), idv(i + 1, j));
		if (v[i][j] == 3 && !lv[i][j] && !lv[i + 1][j])
			b.merge({i, j}, {i + 1, j});
		if (v[i][j] == 3 && lv[i][j] && !lv[i + 1][j]) {
			b[ {i + 1, j}].ins01(col[i][j], lv[i][j]);
		}
		if (v[i][j] == 3 && !lv[i][j] && lv[i + 1][j]) {
			b[ {i, j}].ins01(col[i + 1][j], lv[i + 1][j]);
		}
	}
}
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		if (!lv[i][j]) {
			b[ {i, j}].insp(i, j);
		}
	}
}
for (int i = q - 1; i >= 0; --i) {
	int ans = -1;
	int x = piece[i].x, y = piece[i].y;
	int lvx = lv[x][y], colx = col[x][y];
	lv[x][y] = 0;
	col[x][y] = -1;

	if (h[x][y] == 2 && !lv[x][y] && !lv[x][y + 1])
		hseg.merge(idh(x, y), idh(x, y + 1));
	if (h[x][y - 1] == 2 && !lv[x][y - 1] && !lv[x][y])
		hseg.merge(idh(x, y - 1), idh(x, y));
	pii l = hdi(hseg.getl(idh(x, y))), r = hdi(hseg.getr(idh(x, y)));
	ans += r.y - l.y + 1;

	if (v[x][y] == 2 && !lv[x][y] && !lv[x + 1][y])
		vseg.merge(idv(x, y), idv(x + 1, y));
	if (v[x - 1][y] == 2 && !lv[x - 1][y] && !lv[x][y])
		vseg.merge(idv(x - 1, y), idv(x, y));
	pii u = vdi(vseg.getl(idv(x, y))), d = vdi(vseg.getr(idv(x, y)));
	ans += d.x - u.x + 1;

	b[ {x, y}].insp(x, y);
	if (h[x][y] == 3) {
		if (!lv[x][y + 1])
			b.merge({x, y}, {x, y + 1});
		else
			b[ {x, y}].ins01(col[x][y + 1], lv[x][y + 1]);
	}
	if (h[x][y - 1] == 3) {
		if (!lv[x][y - 1])
			b.merge({x, y - 1}, {x, y});
		else
			b[ {x, y}].ins01(col[x][y - 1], lv[x][y - 1]);
	}
	if (v[x][y] == 3) {
		if (!lv[x + 1][y])
			b.merge({x, y}, {x + 1, y});
		else
			b[ {x, y}].ins01(col[x + 1][y], lv[x + 1][y]);
	}
	if (v[x - 1][y] == 3) {
		if (!lv[x - 1][y])
			b.merge({x - 1, y}, {x, y});
		else
			b[ {x, y}].ins01(col[x - 1][y], lv[x - 1][y]);
	}
	b[ {x, y}].era01(colx, lvx);
	ans += b[ {x, y}].getsz(colx, lvx);
	ans -= b[ {x, y}].geth(l.x, l.y, r.y, colx, lvx);
	ans -= b[ {x, y}].getv(u.x, d.x, u.y, colx, lvx);

	if (col[l.x][l.y - 1] == 1 - colx && h[l.x][l.y - 1] == 2 && lv[l.x][l.y - 1] <= lvx)
		++ans, --l.y;
	if (col[r.x][r.y + 1] == 1 - colx && h[r.x][r.y  ] == 2 && lv[r.x][r.y + 1] <= lvx)
		++ans, ++r.y;
	if (col[u.x - 1][u.y] == 1 - colx && v[u.x - 1][u.y] == 2 && lv[u.x - 1][u.y] <= lvx)
		++ans, --u.x;
	if (col[d.x + 1][d.y] == 1 - colx && v[d.x  ][d.y] == 2 && lv[d.x + 1][d.y] <= lvx)
		++ans, ++d.x;

	auto check = [&](int p, int q) {
		return !lv[p][q] || (col[p][q] == 1 - colx && lv[p][q] <= lvx);
	};
	auto vis = [&](int p, int q) {
		if (b._({p, q}) == b._({x, y}))
			return 1;
		if (lv[p][q] && exist(lv[p][q], col[p][q] ? b[ {x, y}].rt1: b[ {x, y}].rt0, 1, ::q))
			return 1;
		return 0;
	};
	if (h[x][y] == 1 && check(x, y + 1) && !vis(x, y + 1))
		++ans;
	if (v[x][y] == 1 && check(x + 1, y) && !vis(x + 1, y))
		++ans;
	if (h[x][y - 1] == 1 && check(x, y - 1) && !vis(x, y - 1))
		++ans;
	if (v[x - 1][y] == 1 && check(x - 1, y) && !vis(x - 1, y))
		++ans;
	::ans[i] = ans;
}
for (int i = 0; i < q; i++)
	cout << ans[i] << "\n";
qsum += q;

}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) {
mian();
}
}