//#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int H, W;
vector<int> R, C;
vector<vector<int>> A;
const int INF = 1e9;
struct SegTree {
struct Node {
int mi;
int v;
int p;
Node(int _m, int _v, int _p) : mi(_m),v(_v),p(_p) {}
Node() : mi(INF),v(0),p(0) {}
};
vector<Node> seg;
int MAX;
void init(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
for(i=MAX/2;i<MAX;i++) {
seg[i].mi = 0;
seg[i].v = 1;
}
}
Node f(Node x, Node y) {
if(x.mi>y.mi) return y;
if(x.mi<y.mi) return x;
x.v += y.v;
return x;
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = f(seg[2*i],seg[2*i+1]);
}
}
void prop(int n, int ns, int ne) {
if(seg[n].p) {
seg[n].mi += seg[n].p;
if(n<MAX/2) {
seg[2*n].p += seg[n].p;
seg[2*n+1].p += seg[n].p;
}
seg[n].p = 0;
}
}
void add(int s, int e, int k, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n].p += k;
prop(n,ns,ne);
return;
}
int mid = ns + ne >> 1;
add(s,e,k,2*n,ns,mid);
add(s,e,k,2*n+1,mid,ne);
if(n<MAX/2) seg[n] = f(seg[2*n],seg[2*n+1]);
}
Node sum(int s, int e, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return Node(INF,0,0);
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
return f(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
}
int sum(int s, int e) {
return sum(s,e,1,0,MAX/2).v;
}
};
SegTree tree;
int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1};
bool in(int x, int y) {
return 0 <=x && x < H && 0 <= y && y < W;
}
int B[1000005];
void calc(int a, int b, bool inv, bool offline) {
int i, j;
vector<int> V;
for(i=0;i<4;i++) {
int a2 = a + dx[i];
int b2 = b + dy[i];
if(in(a2, b2)) V.push_back(A[a2][b2]);
else V.push_back(H*W);
}
sort(V.begin(),V.end());
int rev = (inv ? -1 : 1);
if(offline) {
B[V[0]]++;
B[V[1]]--;
B[V[2]]+=5;
B[V[3]]-=5;
}
else {
tree.add(V[0], V[1], 1*rev, 1, 0, tree.MAX/2);
tree.add(V[2], V[3], 5*rev, 1, 0, tree.MAX/2);
}
}
void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
H = _H;
W = _W;
R = _R;
C = _C;
A.resize(H);
int i, j;
for(i=0;i<H;i++) A[i].resize(W);
for(i=0;i<R.size();i++) {
A[R[i]][C[i]] = i;
}
tree.init(H*W+3);
//tree.cons();
for(i=-1;i<H;i++) {
for(j=-1;j<W;j++) {
calc(i, j, false, true);
}
}
int MAX = tree.MAX;
int sum2 = 0;
for(i=0;i<H*W;i++) {
sum2 += B[i];
//tree.add(i, i+1, sum2, 1, 0, MAX/2);
tree.seg[i+MAX/2].mi = sum2;
}
tree.cons();
}
void swapping(int a, int b) {
swap(A[R[a]][C[a]],A[R[b]][C[b]]);
swap(R[a], R[b]);
swap(C[a], C[b]);
}
int mx[4] = {0,0,-1,-1};
int my[4] = {0,-1,0,-1};
int swap_seats(int a, int b) {
int i, j;
swapping(a, b);
for(i=0;i<4;i++) {
calc(R[a]+mx[i], C[a]+my[i], false, false);
}
for(i=0;i<4;i++) {
calc(R[b]+mx[i], C[b]+my[i], false, false);
}
swapping(a, b);
for(i=0;i<4;i++) {
calc(R[a]+mx[i], C[a]+my[i], true, false);
}
for(i=0;i<4;i++) {
calc(R[b]+mx[i], C[b]+my[i], true, false);
}
swapping(a, b);
return tree.sum(0, H*W);
}
