#include<bits/stdc++.h>
#define breturn return
#define f first
#define s second
using namespace std;
int h, w, lol, xd, q, arr[1100101], n, bn, sus;
int dx[] = {-1, -1, 0, 0};
int dy[] = {0, -1, -1, 0};
pair<int, int> tour[2201000];
int laz[2200100];
vector<vector<int> > mat;
vector<int> r, c, cum, ab, bb;
pair<pair<int, int>, pair<int, int> > get_interval(int x, int y) {
int val[] = {mat[x][y], mat[x + 1][y], mat[x][y + 1], mat[x + 1][y + 1]};
sort(val, val + 4);
breturn {{val[0], val[1]}, {val[2], val[3]}};
}
void acom(int x) {
if(tour[x * 2].f == tour[x * 2 + 1].f) tour[x] = {tour[x * 2].f, tour[x * 2].s + tour[x * 2 + 1].s};
else if(tour[x * 2].f < tour[x * 2 + 1].f) tour[x] = tour[x * 2];
else tour[x] = tour[x * 2 + 1];
}
void upd(int ax, int bx, int val, int x = 1, int l = 0, int r = bn - 1) {
if(ax > bx) breturn;
if(l >= ax and r <= bx) laz[x] += val;
tour[x].f += laz[x];
if(x < bn) laz[x * 2] += laz[x], laz[x * 2 + 1] += laz[x];
laz[x] = 0;
if((l >= ax and r <= bx) or l > bx or r < ax) breturn;
int mid = (l + r)/2;
upd(ax, bx, val, x * 2, l, mid);
upd(ax, bx, val, x * 2 + 1, mid + 1, r);
acom(x);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
for(int i = 0; i < h * w; i++) c.push_back(C[i] + 1), r.push_back(R[i] + 1);
n = h * w;
for(int i = 0; i < w + 2; i++) cum.push_back(h * w);
for(int i = 0; i < h + 2; i++) mat.push_back(cum);
for(int i = 0; i < h * w; i++) mat[r[i]][c[i]] = i;
for(int i = 0; i < h + 1; i++) for(int j = 0; j < w + 1; j++) {
auto p = get_interval(i, j);
arr[p.f.f]++;
arr[p.f.s]--;
arr[p.s.f]++;
arr[p.s.s]--;
}
for(bn = 1; bn < n; bn *= 2);
for(int i = 0; i < bn; i++) tour[i + bn] = {1e9, 0};
for(int i = 0; i < n; i++) {
sus += arr[i];
tour[i + bn] = {sus, 1};
}
for(int i = bn - 1; i; i--) acom(i);
}
int swap_seats(int a, int b) {
for(int j = 0; j < 4; j++) {
auto p = get_interval(r[a] + dx[j], c[a] + dy[j]);
upd(p.f.f, p.f.s - 1, -1);
upd(p.s.f, p.s.s - 1, -1);
p = get_interval(r[b] + dx[j], c[b] + dy[j]);
upd(p.f.f, p.f.s - 1, -1);
upd(p.s.f, p.s.s - 1, -1);
}
swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for(int j = 0; j < 4; j++) {
auto p = get_interval(r[a] + dx[j], c[a] + dy[j]);
upd(p.f.f, p.f.s - 1, 1);
upd(p.s.f, p.s.s - 1, 1);
p = get_interval(r[b] + dx[j], c[b] + dy[j]);
upd(p.f.f, p.f.s - 1, 1);
upd(p.s.f, p.s.s - 1, 1);
}
if(tour[1].f == 4) breturn tour[1].s;
breturn 0;
}
