#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
vi mat[MAXN];
bool bio[MAXN];
ii pos[MAXN];
int sz;
struct tournament{
ii seg[trsz];
int p[trsz];
ii merge(ii a, ii b){
if(a.X != b.X) return min(a, b);
return {a.X, a.Y + b.Y};
}
tournament(){
fill(p, p + trsz, 0);
for(int i=off; i<trsz; i++) seg[i] = {0, 1};
for(int i=off-1; i; i--) seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void prop(int x){
if(p[x] == 0) return;
seg[x].X += p[x];
if(x < off) p[x * 2] += p[x], p[x * 2 + 1] += p[x];
p[x] = 0;
}
void update(int x, int lo, int hi, int a, int b, int vl){
if(a >= b) return;
prop(x);
if(lo >= b or hi <= a) return;
if(lo >= a and hi <= b){
p[x] = vl;
prop(x);
return;
}
int mid = (lo + hi) / 2;
update(x * 2, lo, mid, a, b, vl);
update(x * 2 + 1, mid, hi, a, b, vl);
seg[x] = merge(seg[x * 2], seg[x * 2 + 1]);
}
ii query(int x, int lo, int hi, int a, int b){
prop(x);
if(lo >= b or hi <= a) return {inf, 0};
if(lo >= a and hi <= b) return seg[x];
int mid = (lo + hi) / 2;
return merge(query(x * 2, lo, mid, a, b), query(x * 2 + 1, mid, hi, a, b));
}
int qry(int l, int r){
ii vl = query(1, 0, off, l, r);
if(vl.X == 4) return vl.Y;
return 0;
}
}t;
int vec[4];
void add(int i, int j, int vl){
for(int di=0; di<=1; di++){
for(int dj=0; dj<=1; dj++){
vec[di * 2 + dj] = mat[i + di][j + dj];
}
}
sort(vec, vec + 4);
t.update(1, 0, off, vec[0], vec[1], 1 * vl);
t.update(1, 0, off, vec[2], vec[3], 5 * vl);
}
int stup;
void give_initial_chart(int r, int s, vi a, vi b){
sz = r * s;
stup = s;
for(int i=0; i<r+2; i++) mat[i].resize(s + 2, sz);
for(int i=0; i<sz; i++){
mat[a[i] + 1][b[i] + 1] = i;
pos[i] = {a[i] + 1, b[i] + 1};
}
for(int i=0; i<=r; i++) for(int j=0; j<=s; j++) add(i, j, 1);
}
ii del[8];
int swap_seats(int a, int b){
int r1, s1, r2, s2;
tie(r1, s1) = pos[a];
tie(r2, s2) = pos[b];
int s = 0;
for(int i=-1; i<=0; i++){
for(int j=-1; j<=0; j++){
if(!bio[(r1 + i) * stup + s1 + j]) del[s++] = {r1 + i, s1 + j};
if(!bio[(r2 + i) * stup + s2 + j]) del[s++] = {r2 + i, s2 + j};
bio[(r1 + i) * stup + s1 + j] = 1;
bio[(r2 + i) * stup + s2 + j] = 1;
}
}
for(int i=0; i<s; i++){
add(del[i].X, del[i].Y, -1);
bio[del[i].X * stup + del[i].Y] = 0;
}
swap(pos[a], pos[b]);
swap(mat[r1][s1], mat[r2][s2]);
for(int i=0; i<s; i++) add(del[i].X, del[i].Y, 1);
return t.qry(0, sz);
}
