#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pf printf
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
#define maxn 4000005
int h,w,n;
vector<int> r,c;
vector<vector<int>> a;
int lz[maxn];
ii v[maxn];//{min element,#min}
void init(int i,int s,int e){
v[i]={0,e-s+1};
if(s!=e){
int m=(s+e)>>1;
init(2*i+1,s,m);
init(2*i+2,m+1,e);
}
}
void ppo(int i,int s,int e){
v[i].fi+=lz[i];
if(s!=e){
int m=(s+e)>>1;
lz[2*i+1]+=lz[i];
lz[2*i+2]+=lz[i];
}
lz[i]=0;
}
void up(int i,int s,int e,int x,int y,int nv){
if(s==x&&e==y){lz[i]+=nv;return;}
int m=(s+e)>>1;
if(y<=m)up(2*i+1,s,m,x,y,nv);
else if(x>m)up(2*i+2,m+1,e,x,y,nv);
else up(2*i+1,s,m,x,m,nv),up(2*i+2,m+1,e,m+1,y,nv);
ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
if(v[2*i+1].fi==v[2*i+2].fi)v[i]={v[2*i+1].fi,v[2*i+1].se+v[2*i+2].se};
else v[i]=min(v[2*i+1],v[2*i+2]);
}
inline void up(int x,int y,int nv){
if(x>y)return;
up(0,0,n-1,x,y,nv);
}
inline int qry(){
if(v[0].fi+lz[0]==4)return v[0].se;
return 0;
}
inline void upd(int r,int c,int m){//update 2x2 with (r,c) as top left
vector<int> v={a[r][c],a[r][c+1],a[r+1][c],a[r+1][c+1]};
sort(all(v));
up(v[0],v[1]-1,m*1);//3 white 1 black, +-1
up(v[2],v[3]-1,m*5);//3 black 1 white, +-inf(=5 since max is 4)
}
inline void upd2(int r,int c,int m){//update all squares containing (r,c)
upd(r,c,m);
upd(r-1,c,m);
upd(r,c-1,m);
upd(r-1,c-1,m);
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
h=H;w=W;n=h*w;
for(int i:R)r.pb(i+1);
for(int i:C)c.pb(i+1);
a.resize(h+2);
for(int i=0;i<h+2;++i){
a[i].resize(w+2,h*w);
}
for(int i=0;i<h*w;++i){
a[r[i]][c[i]]=i;
}
init(0,0,n-1);
for(int i=0;i<=h;++i){
for(int j=0;j<=w;++j){
upd(i,j,1);
}
}
}
int swap_seats(int x,int y){
upd2(r[x],c[x],-1);
upd2(r[y],c[y],-1);
swap(a[r[x]][c[x]],a[r[y]][c[y]]);
swap(r[x],r[y]);
swap(c[x],c[y]);
upd2(r[x],c[x],1);
upd2(r[y],c[y],1);
return qry();
}
