#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "seats.h"
struct pt
{
int mi3,mi1,slmi;
friend pt operator + (pt a,pt b)
{
if(a.mi3<b.mi3) return a;
if(b.mi3<a.mi3) return b;
if(a.mi1<b.mi1) return a;
if(b.mi1<a.mi1) return b;
return { a.mi3,a.mi1,a.slmi+b.slmi };
}
};
struct Interval_Tree
{
pt st[4*maxn];
int lz3[4*maxn],lz1[4*maxn];
void change(int id,int k3,int k1)
{
st[id].mi3+=k3;
st[id].mi1+=k1;
lz3[id]+=k3;
lz1[id]+=k1;
}
void down(int id)
{
change(id*2,lz3[id],lz1[id]);
change(id*2+1,lz3[id],lz1[id]);
lz3[id]=lz1[id]=0;
}
void build(int id,int l,int r)
{
if(l==r) { st[id]={ 0,0,1 }; return ; }
int mid=(l+r)>>1;
build(id*2,l,mid); build(id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
void update(int id,int l,int r,int u,int v,int k3,int k1)
{
if(u>r || v<l) return ;
if(u<=l && r<=v) { change(id,k3,k1); return ; }
down(id);
int mid=(l+r)>>1;
update(id*2,l,mid,u,v,k3,k1); update(id*2+1,mid+1,r,u,v,k3,k1);
st[id]=st[id*2]+st[id*2+1];
}
} IT;
vector <int> a[maxn];
int n,m,x[maxn],y[maxn],i,j;
void Work(int x,int y,int k)
{
if(a[x][y]==-1 || a[x][y+1]==-1 || a[x+1][y]==-1 || a[x+1][y+1]==-1) return ;
vector <int> vec;
vec.push_back(a[x][y]);
vec.push_back(a[x][y+1]);
vec.push_back(a[x+1][y]);
vec.push_back(a[x+1][y+1]);
sort(vec.begin(),vec.end());
IT.update(1,1,n*m,vec[0],vec[1]-1,0,k);
IT.update(1,1,n*m,vec[2],vec[3]-1,k,0);
}
void give_initial_chart(int _n,int _m,vector <int> _X,vector <int> _Y)
{
n=_n; m=_m;
for(i=0;i<n*m;i++) x[i+1]=_X[i]+1,y[i+1]=_Y[i]+1;
for(i=0;i<=n+1;i++) a[i].resize(m+2);
for(i=1;i<=n*m;i++) a[x[i]][y[i]]=i;
for(i=0;i<=m+1;i++) a[0][i]=a[n+1][i]=n*m+1;
for(i=1;i<=n;i++) a[i][0]=a[i][m+1]=n*m+1;
IT.build(1,1,n*m);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++) Work(i,j,1);
}
int swap_seats(int u,int v)
{
u++; v++;
Work(x[u]-1,y[u]-1,-1);
Work(x[u]-1,y[u],-1);
Work(x[u],y[u]-1,-1);
Work(x[u],y[u],-1);
a[x[u]][y[u]]=-1;
Work(x[v]-1,y[v]-1,-1);
Work(x[v]-1,y[v],-1);
Work(x[v],y[v]-1,-1);
Work(x[v],y[v],-1);
a[x[v]][y[v]]=-1;
swap(x[u],x[v]);
swap(y[u],y[v]);
a[x[u]][y[u]]=u;
Work(x[u]-1,y[u]-1,1);
Work(x[u]-1,y[u],1);
Work(x[u],y[u]-1,1);
Work(x[u],y[u],1);
a[x[v]][y[v]]=v;
Work(x[v]-1,y[v]-1,1);
Work(x[v]-1,y[v],1);
Work(x[v],y[v]-1,1);
Work(x[v],y[v],1);
return IT.st[1].slmi;
}
/*
int main()
{
freopen("seats.inp","r",stdin);
freopen("seats.out","w",stdout);
int n,m,q,i,x,y,k;
vector <int> X,Y;
cin>>n>>m>>q;
for(i=1;i<=n*m;i++) cin>>x>>y,X.push_back(x),Y.push_back(y);
give_initial_chart(n,m,X,Y);
for(i=1;i<=q;i++) cin>>x>>y,cout<<swap_seats(x,y)<<'\n';
}
*/
