#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,seg[4000009],segmn[4000009],seg2[4000009],n,l,r,z,zz,za,jm[4000009];
pair <int, int> p[1000009];
vector <vector <int> > f;
void pushdown(int q, int w, int rr){
if(q!=w){
seg2[rr*2]+=seg2[rr];
seg2[rr*2+1]+=seg2[rr];
}
segmn[rr]+=seg2[rr];
seg2[rr]=0;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]=z;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
if(segmn[rr*2]<segmn[rr*2+1]){
seg[rr]=seg[rr*2];
segmn[rr]=segmn[rr*2];
}
if(segmn[rr*2+1]<segmn[rr*2]){
seg[rr]=seg[rr*2+1];
segmn[rr]=segmn[rr*2+1];
}
if(segmn[rr*2]==segmn[rr*2+1]){
seg[rr]=seg[rr*2]+seg[rr*2+1];
segmn[rr]=segmn[rr*2];
}
}
void read(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
if(z>segmn[rr]){
zz=seg[rr];
z=segmn[rr];
}else{
if(z==segmn[rr]){
zz+=seg[rr];
}
}
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void update(int q, int w, int rr){
int X[6];
X[1]=f[q][w];
X[2]=f[q+1][w];
X[3]=f[q][w+1];
X[4]=f[q+1][w+1];
sort(X+1,X+5);
l=X[1];r=X[2]-1;z=rr;
if(l<=r) upd(1,za,1);
l=X[3];r=X[4]-1;z=rr*6;
if(l<=r) upd(1,za,1);
}
void update2(int q, int w, int rr){
int X[6];
X[1]=f[q][w];
X[2]=f[q+1][w];
X[3]=f[q][w+1];
X[4]=f[q+1][w+1];
sort(X+1,X+5);
l=X[1];r=X[2]-1;z=rr;
if(l<=r){
jm[l]+=z;
jm[r+1]-=z;
}
l=X[3];r=X[4]-1;z=rr*6;
if(l<=r){
jm[l]+=z;
jm[r+1]-=z;
}
}
void bld(int q, int w, int rr){
segmn[rr]=0;seg[rr]=w-q+1;
if(q==w) return;
bld(q,(q+w)/2,rr*2);
bld((q+w)/2+1,w,rr*2+1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
a=H;b=W;
n=a*b;
f.resize(H+6);
za=1;
while(za<n+6) za*=2;
bld(1,za,1);
for(i=0; i<=H+4; i++){
f[i].resize(W+6);
}
for(i=1; i<=H*W; i++){
R[i-1]++;C[i-1]++;
p[i].first=R[i-1];
p[i].second=C[i-1];
f[R[i-1]][C[i-1]]=i;
}
for(i=0; i<=H+1; i++){
f[i][0]=f[i][W+1]=n+4;
}
for(i=0; i<=W+1; i++){
f[0][i]=f[H+1][i]=n+4;
}
for(i=0; i<=H; i++){
for(j=0; j<=W; j++){
update2(i,j,1);
}
}
for(i=1; i<=za; i++){
jm[i]+=jm[i-1];
seg[za+i-1]=1;
segmn[za+i-1]=jm[i];
}
for(int rr=za-1; rr>=1; rr--){
if(segmn[rr*2]<segmn[rr*2+1]){
seg[rr]=seg[rr*2];
segmn[rr]=segmn[rr*2];
}
if(segmn[rr*2+1]<segmn[rr*2]){
seg[rr]=seg[rr*2+1];
segmn[rr]=segmn[rr*2+1];
}
if(segmn[rr*2]==segmn[rr*2+1]){
seg[rr]=seg[rr*2]+seg[rr*2+1];
segmn[rr]=segmn[rr*2];
}
}
}
void UPD(int q, int w, int rr){
update(q-1,w-1,rr);
update(q-1,w,rr);
update(q,w-1,rr);
update(q,w,rr);
}
int swap_seats(int C, int D) {
C++;D++;
c=C;d=D;
UPD(p[c].first,p[c].second,-1);
f[p[c].first][p[c].second]=d;
UPD(p[c].first,p[c].second,1);
UPD(p[d].first,p[d].second,-1);
f[p[d].first][p[d].second]=c;
UPD(p[d].first,p[d].second,1);
swap(p[c],p[d]);
z=n+2;zz=0;
l=1;r=n;
read(1,za,1);
if(z!=4){
return 0;
}else{
return zz;
}
}
