#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define lv (v + 1)
#define rv (v + 2 * (mid - l + 1))
using namespace std;
using ll = long long;
const int N = 1100000;
int h, w, n, r[N], c[N], vec[N];
int get(int i, int j) {
if (i < 1 || j < 1 || i > h || j > w)
return n + 1;
i--; j--;
return vec[i * w + j];
}
int vv[2 * N][16], uu[2 * N][7];
void merge(int v, int l, int r) {
for (int i = 0; i < 16; i++)
vv[v][i] = 0;
if (uu[v][6] || uu[v][4])
return;
if (l == r) {
vv[v][uu[v][5]] = 1;
return;
}
int mid = (l + r) / 2;
for (int i = 0; i < 16; i++)
vv[v][i] = vv[lv][i] + vv[rv][i];
if (uu[v][5]) {
for (int i = 15; i >= 0; i--) {
if ((i & uu[v][5]) == 0)
vv[v][i | uu[v][5]] += vv[v][i];
vv[v][i] = 0;
}
}
}
void build(int v, int l, int r) {
if (l != r) {
int mid = (l + r) / 2;
build(lv, l, mid);
build(rv, mid + 1, r);
}
merge(v, l, r);
}
void upd(int v, int l, int r, int ql, int qr, int m, int k) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
if (uu[v][k] > 1) uu[v][6]--;
uu[v][k] += m;
uu[v][5] ^= (1 << k);
if (uu[v][k] > 1) uu[v][6]++;
merge(v, l, r);
return;
}
int mid = (l + r) / 2;
upd(lv, l, mid, ql, qr, m, k);
upd(rv, mid + 1, r, ql, qr, m, k);
merge(v, l, r);
}
vector<array<int, 4>> pp;
void resolve() {
sort(begin(pp), end(pp));
int x = -1, y = -1, z = -1, w = -1;
for (auto [a, b, c, d] : pp) {
if (a != x || b != y || c != z) {
if (x != -1 && w != 0)
upd(1, 1, n, x, y, w, z);
x = a, y = b, z = c, w = d;
} else w += d;
}
if (x != -1 && w != 0)
upd(1, 1, n, x, y, w, z);
pp.clear();
}
void upd(int i, int j, int m) {
int a = get(i, j);
int b = get(i, j + 1);
int c = get(i + 1, j);
int d = get(i + 1, j + 1);
vector<int> v = {a, b, c, d};
sort(begin(v), end(v));
int l = v[0], r = v[1] - 1;
if (l <= r) {
if (v[0] == a) {pp.push_back({l, r, 0, m});}
if (v[0] == b) {pp.push_back({l, r, 1, m});}
if (v[0] == c) {pp.push_back({l, r, 2, m});}
if (v[0] == d) {pp.push_back({l, r, 3, m});}
}
l = v[2], r = v[3] - 1;
if (l <= r) {
if (v[3] == a) {pp.push_back({l, r, 4, m});}
}
}
int ans() {
return vv[1][15];
}
void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
h = _H;
w = _W;
n = h * w;
for (int i = 1; i <= n; i++)
vec[(r[i] = _R[i - 1]) * w + (c[i] = _C[i - 1])] = i;
build(1, 1, n);
for (int i = 0; i <= h; i++)
for (int j = 0; j <= w; j++)
upd(i, j, 1);
resolve();
}
int swap_seats(int a, int b) {
a++; b++;
vector<array<int, 2>> pos;
for (int i = -1; i <= 0; i++)
for (int j = -1; j <= 0; j++) {
pos.push_back({r[a] + i + 1, c[a] + j + 1});
pos.push_back({r[b] + i + 1, c[b] + j + 1});
}
sort(begin(pos), end(pos));
pos.erase(unique(begin(pos), end(pos)), end(pos));
for (auto [x, y] : pos)
upd(x, y, -1);
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(vec[r[a] * w + c[a]], vec[r[b] * w + c[b]]);
for (auto [x, y] : pos)
upd(x, y, 1);
resolve();
return ans();
}
#ifdef LOCAL
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}
#endif
