#include <bits/stdc++.h>
#ifndef HOME
#include "seats.h"
#endif
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
const int A = 1e6 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct Nod {
int min, cnt, lazy;
};
int f[A];
vector<vector<int>> mx;
vector<int> row, col;
int n, m, a;
int ql, qr, qval;
Nod pom[A * 4];
static void prop(int nod) {
pom[2 * nod + 1].lazy+= pom[nod].lazy;
pom[2 * nod].lazy+= pom[nod].lazy;
pom[nod].min+= pom[nod].lazy;
pom[nod].lazy = 0;
}
static void update(int nod, int st, int dr) {
if (qr < ql)
return;
if (ql <= st && dr <= qr) {
pom[nod].lazy+= qval;
return;
}
int mid = (st + dr) / 2;
prop(nod);
if (ql <= mid)
update(2 * nod, st, mid);
if (mid < qr)
update(2 * nod + 1, mid + 1, dr);
pom[nod].min = min(pom[2 * nod].min + pom[2 * nod].lazy, pom[2 * nod + 1].min + pom[2 * nod + 1].lazy);
pom[nod].cnt = (pom[nod].min == pom[2 * nod].min + pom[2 * nod].lazy ? pom[2 * nod].cnt : 0);
pom[nod].cnt+= (pom[nod].min == pom[2 * nod + 1].min + pom[2 * nod + 1].lazy ? pom[2 * nod + 1].cnt : 0);
}
static pii query(int nod, int st, int dr) {
if (ql <= st && dr <= qr)
return pii(pom[nod].min + pom[nod].lazy, pom[nod].cnt);
int mid = (st + dr) / 2;
pii ans = {1e9, 1e9};
prop(nod);
if (ql <= mid)
ans = query(2 * nod, st, mid);
if (mid < qr) {
pii ret = query(2 * nod + 1, mid + 1, dr);
if (ret.x < ans.x)
ans = ret;
else if (ret.x == ans.x)
ans.y+= ret.y;
}
return ans;
}
static void baga(int idx, int qt = 1) {
vector<pii> nidx;
if (idx == a)
return;
int x = row[idx], y = col[idx];
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
int val = mx[nx][ny];
nidx.emplace_back(val, dir);
}
sort(begin(nidx), end(nidx));
if (nidx[1].x < idx) {
ql = nidx[1].x;
qr = idx - 1;
qval = 100 * qt;
update(1, 0, a);
}
ql = idx;
qr = nidx[0].x - 1;
qval = 10 * qt;
update(1, 0, a);
ql = max(idx, nidx[0].x);
qr = nidx[1].x - 1;
qval = 2 * qt;
update(1, 0, a);
if (nidx[0].y % 2 == nidx[1].y % 2)
return;
ql = max(idx, nidx[1].x);
qr = nidx[2].x - 1;
qval = qt;
update(1, 0, a);
}
static void scoate(int idx) {
baga(idx, -1);
}
static void show() {
for (int i = 1; i <= n; ++i, cout << '\n')
for (int j = 1; j <= m; ++j)
cout << mx[i][j] << ' ';
for (int i = 0; i < a; ++i) {
ql = qr = i;
cout << query(1, 0, a).x << ' '; }
cout << endl;
}
static void meh(int nod, int st, int dr) {
if (st == dr) {
pom[nod].cnt = 1;
return;
}
int mid = (st + dr) / 2;
meh(2 * nod, st, mid);
meh(2 * nod + 1, mid + 1, dr);
pom[nod].cnt = dr - st + 1;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
swap(row, R);
swap(col, C);
n = H;
m = W;
a = n * m;
mx = vector<vector<int>>(n + 5, vector<int>(m + 5));
for (int i = 0; i < a; ++i)
mx[++row[i]][++col[i]] = i;
for (int i = 0; i <= n + 1; ++i)
mx[i][0] = mx[i][m + 1] = a;
for (int j = 0; j <= m + 1; ++j)
mx[0][j] = mx[n + 1][j] = a;
meh(1, 0, a);
for (int i = 0; i < a; ++i)
baga(i);
}
int swap_seats(int u, int v) {
static int call = 0; ++call;
int xu = row[u], yu = col[u];
int xv = row[v], yv = col[v];
scoate(u);
scoate(v);
for (int dir = 0; dir < 4; ++dir) {
int nx = xu + dx[dir];
int ny = yu + dy[dir];
scoate(mx[nx][ny]);
}
for (int dir = 0; dir < 4; ++dir) {
int nx = xv + dx[dir];
int ny = yv + dy[dir];
scoate(mx[nx][ny]);
}
swap(mx[xu][yu], mx[xv][yv]);
swap(col[u], col[v]);
swap(row[u], row[v]);
baga(u);
baga(v);
for (int dir = 0; dir < 4; ++dir) {
int nx = xu + dx[dir];
int ny = yu + dy[dir];
baga(mx[nx][ny]);
}
for (int dir = 0; dir < 4; ++dir) {
int nx = xv + dx[dir];
int ny = yv + dy[dir];
baga(mx[nx][ny]);
}
ql = 1, qr = a - 1;
return 1 + query(1, 0, a).y;
}
#ifdef HOME
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() {
freopen("seats.in", "r", stdin);
freopen("seats.out", "w", stdout);
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
