#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,m,a[1000069],ya[1000069],xa[1000069],vy[4]={-1,0,1,0},vx[4]={0,1,0,-1},inf=1e9;
pair<int,int> ps[1000069];
bool alr=0;
struct segtree
{
int l,r,c;
pair<int,int> mn,lz={0,0};
segtree *p[2];
void bd(int lh,int rh)
{
l=lh;
r=rh;
if(l==r)
{
mn=ps[l];
mn.sc+=l+1;
c=1;
}
else
{
int ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
mn=min(p[0]->mn,p[1]->mn);
c=p[0]->c*(p[0]->mn==mn)+p[1]->c*(p[1]->mn==mn);
}
}
inline void blc()
{
if(lz!=mp(0,0))
{
int ii;
for(ii=0;ii<2;ii++)
{
p[ii]->mn.fr+=lz.fr;
p[ii]->mn.sc+=lz.sc;
p[ii]->lz.fr+=lz.fr;
p[ii]->lz.sc+=lz.sc;
}
lz={0,0};
}
}
void ud(int ky,int lh,int rh,int w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
if(!ky)
{
mn.fr+=w;
lz.fr+=w;
}
else
{
mn.sc+=w;
lz.sc+=w;
}
}
else
{
int ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(ky,lh,rh,w);
}
mn=min(p[0]->mn,p[1]->mn);
c=p[0]->c*(p[0]->mn==mn)+p[1]->c*(p[1]->mn==mn);
}
}
}
sg;
void acv(int y,int x,int u)
{
int i,j,im,p=y*m+x,yy,xx,pp,mn[2]={inf,inf};
for(im=0;im<4;im++)
{
yy=y+vy[im];
xx=x+vx[im];
if(yy>=0&&xx>=0&&yy<n&&xx<m)
{
pp=yy*m+xx;
for(i=0;i<2;i++)
{
if(a[pp]<mn[i])
{
for(j=1;j>i;j--)
{
mn[j]=mn[j-1];
}
mn[i]=a[pp];
break;
}
}
}
}
if(alr)
{
sg.ud(0,mn[1],a[p]-1,u);
}
else if(mn[1]<=a[p])
{
ps[mn[1]].fr+=u;
ps[a[p]].fr-=u;
}
}
void give_initial_chart(int on,int om,vector<int> yaa,vector<int> xaa)
{
int i,j,p;
n=on;
m=om;
for(i=0;i<n*m;i++)
{
ya[i]=yaa[i];
xa[i]=xaa[i];
a[ya[i]*m+xa[i]]=i;
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
p=i*m+j;
acv(i,j,1);
if(i)
{
ps[max(a[p],a[p-m])].sc--;
}
if(j)
{
ps[max(a[p],a[p-1])].sc--;
}
if(i&&j)
{
ps[max(max(a[p],a[p-1]),max(a[p-m],a[p-m-1]))].sc++;
}
}
}
for(i=1;i<n*m;i++)
{
ps[i].fr+=ps[i-1].fr;
ps[i].sc+=ps[i-1].sc;
}
sg.bd(0,n*m-1);
alr=1;
}
int swap_seats(int w,int w2)
{
int i,ii,iii,im,u,y,x,p,yy,xx,pp;
for(ii=0;ii<2;ii++)
{
y=ya[w];
x=xa[w];
p=y*m+x;
for(iii=0;iii<2;iii++)
{
u=iii*2-1;
acv(y,x,u);
for(im=0;im<4;im++)
{
yy=y+vy[im];
xx=x+vx[im];
if(yy>=0&&xx>=0&&yy<n&&xx<m)
{
pp=yy*m+xx;
acv(yy,xx,u);
sg.ud(1,max(a[p],a[pp]),n*m-1,-u);
}
yy=y+im/2;
xx=x+im%2;
if(yy>0&&xx>0&&yy<n&&xx<m)
{
pp=yy*m+xx;
sg.ud(1,max(max(a[pp],a[pp-1]),max(a[pp-m],a[pp-m-1])),n*m-1,u);
}
}
a[p]=w2;
}
swap(w,w2);
}
swap(ya[w],ya[w2]);
swap(xa[w],xa[w2]);
return sg.c;
}
