#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 0;
using namespace std;
struct segtree {
int n;
vector<int> mn, cnt, tag;
segtree() {}
segtree(const vector<int> &a) {
n = a.size();
while (n != (n & -n)) n += (n & -n);
mn.resize(2 * n, 0);
tag.resize(2 * n, 0);
cnt.resize(2 * n, 1);
for (int i = 0; i < a.size(); i++)
mn[i + n - 1] = a[i];
for (int i = n - 2; i >= 0; i--) fix(i);
}
void push(int x) {
mn[x] += tag[x];
if (x < n - 1) {
tag[2 * x + 1] += tag[x];
tag[2 * x + 2] += tag[x];
}
tag[x] = 0;
}
void fix(int x) {
push(2 * x + 1), push(2 * x + 2);
mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
if (mn[2 * x + 1] < mn[2 * x + 2])
cnt[x] = cnt[2 * x + 1];
else if (mn[2 * x + 1] > mn[2 * x + 2])
cnt[x] = cnt[2 * x + 2];
else
cnt[x] = cnt[2 * x + 1] + cnt[2 * x + 2];
}
void upd(int l, int r, int add) {
if (l > r) return;
upd(l, r, add, 0, 0, n - 1);
}
void upd(int l, int r, int add, int node, int nl, int nr) {
if (r < nl || nr < l) return;
if (l <= nl && nr <= r) {
tag[node] += add;
return;
}
push(node);
int mid = (nl + nr) / 2;
upd(l, r, add, 2 * node + 1, nl, mid);
upd(l, r, add, 2 * node + 2, mid + 1, nr);
fix(node);
}
int query(int l, int r) {
return query(l, r, 0, 0, n - 1).second;
}
pair<int, int> query(int l, int r, int node, int nl, int nr) {
if (r < nl || nr < l) return{ md, 0 };
push(node);
if (l <= nl && nr <= r) {
return{ mn[node], cnt[node] };
}
int mid = (nl + nr) / 2;
pair<int, int> p1 = query(l, r, 2 * node + 1, nl, mid);
pair<int, int> p2 = query(l, r, 2 * node + 2, mid + 1, nr);
if (p1.first == p2.first) return{ p1.first, p1.second + p2.second };
return min(p1, p2);
}
void print() {
for (int i = 0; i < 2 * n - 1; i++) push(i);
for (int i = n - 1; i < 2 * n - 1; i++) cout << mn[i] << " "; cout << '\n';
}
};
int n, m, en;
vector<int> r, c;
vector<vector<int>> A;
segtree S;
vector<int> pre;
void upd(int i, int j, int add) {
static const int dx[4] = { 0,-1,0,-1 };
static const int dy[4] = { 0,0,-1,-1 };
vector<int> T;
for (int k = 0; k < 4; k++)
if (0 <= i + dx[k] && i + dx[k] < n && 0 <= j + dy[k] && j + dy[k] < m)
T.push_back(A[i + dx[k]][j + dy[k]]);
sort(T.begin(), T.end());
if (T.size() & 1) T.push_back(en);
for (int k = 0; k < T.size(); k += 2) {
if (OO) {
cout << "cell (" << i << ", " << j << ") adds range [" << T[k] << ", " << T[k + 1] - 1 << "]\n";
}
S.upd(T[k], T[k + 1] - 1, add);
}
}
void slowupd(int i, int j, int add) {
static const int dx[4] = { 0,-1,0,-1 };
static const int dy[4] = { 0,0,-1,-1 };
vector<int> T;
for (int k = 0; k < 4; k++)
if (0 <= i + dx[k] && i + dx[k] < n && 0 <= j + dy[k] && j + dy[k] < m)
T.push_back(A[i + dx[k]][j + dy[k]]);
sort(T.begin(), T.end());
if (T.size() & 1) T.push_back(en);
for (int k = 0; k < T.size(); k += 2) {
if (OO) {
cout << "cell (" << i << ", " << j << ") adds range [" << T[k] << ", " << T[k + 1] - 1 << "]\n";
}
pre[T[k]] += add;
if (T[k + 1] < en) pre[T[k + 1]] -= add;
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
en = n * m;
r = R;
c = C;
A.resize(n, vector<int>(m));
for (int i = 0; i < n * m; i++)
A[r[i]][c[i]] = i;
pre.resize(n * m, 0);
for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++)
slowupd(i, j, 1);
for (int i = 1; i < en; i++) pre[i] += pre[i - 1];
S = segtree(pre);
if (OO) {
cout << "the tree\n";
S.print();
}
}
int swap_seats(int a, int b) {
upd(r[a], c[a], -1);
upd(r[a], c[a] + 1, -1);
upd(r[a] + 1, c[a], -1);
upd(r[a] + 1, c[a] + 1, -1);
upd(r[b], c[b], -1);
upd(r[b], c[b] + 1, -1);
upd(r[b] + 1, c[b], -1);
upd(r[b] + 1, c[b] + 1, -1);
swap(A[r[a]][c[a]], A[r[b]][c[b]]);
swap(r[a], r[b]), swap(c[a], c[b]);
upd(r[a], c[a], 1);
upd(r[a], c[a] + 1, 1);
upd(r[a] + 1, c[a], 1);
upd(r[a] + 1, c[a] + 1, 1);
upd(r[b], c[b], 1);
upd(r[b], c[b] + 1, 1);
upd(r[b] + 1, c[b], 1);
upd(r[b] + 1, c[b] + 1, 1);
if (OO) {
cout << "the tree\n";
S.print();
}
return S.query(0, n * m - 1);
}
/*
int main() {
int nn, mm, qq;
cin >> nn >> mm >> qq;
vector<int> rr(nn*mm), cc(nn*mm);
for (auto &i : rr) cin >> i;
for (auto &i : cc) cin >> i;
give_initial_chart(nn, mm, rr, cc);
while (qq--) {
int a, b;
cin >> a >> b;
cout << swap_seats(a, b) << '\n';
}
}
*/
