#include "bits/stdc++.h"
#include "seats.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 1e6 + 5;
const int INF = (int) 1e9;
int n,m,tot=0;
vector<array<int,2>> go;
vector<int> mnr,mxr,mnc,mxc,Cache;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
n=H,m=W;
go.resize(n*m+5);
for(int i=0;i<n*m;i++){
int a=R[i],b=C[i];
go[i]={a,b};
}
Cache.assign(n*m+5,0);
mnr.resize(n*m+5);
mxr.resize(n*m+5);
mnc.resize(n*m+5);
mxc.resize(n*m+5);
int Mnr=INF,Mxr=-INF,Mnc=INF,Mxc=-INF;
for(int i=0;i<n*m;i++){
int a = go[i][0] , b = go[i][1];
Mnr=min(Mnr,a);
Mxr=max(Mxr,a);
Mnc=min(Mnc,b);
Mxc=max(Mxc,b);
mxc[i]=Mxc;
mnr[i]=Mnr;
mxr[i]=Mxr;
mnc[i]=Mnc;
if((Mxc-Mnc+1)*(Mxr-Mnr+1)==i+1){
tot++;
Cache[i]=1;
}
}
}
int swap_seats(int A,int B){
if(A>B) swap(A,B);
swap(go[A],go[B]);
int Mnr=INF,Mxr=-INF,Mnc=INF,Mxc=-INF;
if(A>0){
Mnr=mnr[A-1];
Mxc=mxc[A-1];
Mnc=mnc[A-1];
Mxr=mxr[A-1];
}
for(int i=A;i<=B;i++){
if(Cache[i]){
Cache[i]=0;
tot--;
}
int a = go[i][0] , b = go[i][1];
Mnr=min(Mnr,a);
Mxr=max(Mxr,a);
Mnc=min(Mnc,b);
Mxc=max(Mxc,b);
mxc[i]=Mxc;
mnr[i]=Mnr;
mxr[i]=Mxr;
mnc[i]=Mnc;
if((Mxc-Mnc+1)*(Mxr-Mnr+1)==i+1){
tot++;
Cache[i]=1;
}
}
return tot;
}
/*void _(){
int n,m,q;
cin >> n >> m >> q;
Fenwick F(N,0);
int ar[n+5][m+5];
array<int,2> go[n*m+5];
for(int i=0;i<n*m;i++){
int a,b;
cin >> a >> b;
ar[a][b]=i;
go[i]={a,b};
}
int mnr[n*m+5],mxr[n*m+5],mnc[n*m+5],mxc[n*m+5];
int Mnr=INF,Mxr=-INF,Mnc=INF,Mxc=-INF;
for(int i=0;i<n*m;i++){
int a = go[i][0] , b = go[i][1];
Mnr=min(Mnr,a);
Mxr=max(Mxr,a);
Mnc=min(Mnc,b);
Mxc=max(Mxc,b);
if((Mxc-Mnc+1)*(Mxr-Mnr+1)==i+1) F.upd(i+1,1);
}
cout << F.query(n*m) << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
