#include <bits/stdc++.h>
using namespace std;
const int c=1000002, p=1048576;
int n, m, k, sor[c], pos[c], oszlop[c], kezd[2*p], veg[2*p], kert[2*p], kdb[2*p], lp[2*p], t[4];
bool jo[c];
int st, fi, ert;
void add(int a) {
int k=kezd[a], v=veg[a], x=2*a, y=2*a+1;
if (st>v || fi<k) return;
if (st<=k && v<=fi) lp[a]+=ert;
else {
add(x), add(y);
int p=kert[x]+lp[x], q=kert[y]+lp[y];
kert[a]=min(p, q);
kdb[a]=0;
if (kert[a]==p) kdb[a]+=kdb[x];
if (kert[a]==q) kdb[a]+=kdb[y];
}
}
int ki(int a, int b) {
if (a<0 || a>=n || b<0 || b>=m) return k;
return pos[a*m+b];
}
void upd(int a, int b, int c) {
t[0]=ki(a-1, b-1), t[1]=ki(a-1, b), t[2]=ki(a, b-1), t[3]=ki(a, b);
sort(t, t+4);
ert=c;
if (t[0]!=t[1]) st=t[0], fi=t[1]-1, add(1);
if (t[2]!=t[3]) st=t[2], fi=t[3]-1, add(1);
}
void kupd(int a, int b, int c) {
upd(a+1, b+1, c), upd(a+1, b, c);
upd(a, b+1, c), upd(a, b, c);
}
int swap_seats(int a, int b) {
kupd(sor[a], oszlop[a], -1), kupd(sor[b], oszlop[b], -1);
swap(sor[a], sor[b]), swap(oszlop[a], oszlop[b]);
pos[sor[a]*m+oszlop[a]]=a, pos[sor[b]*m+oszlop[b]]=b;
kupd(sor[a], oszlop[a], 1), kupd(sor[b], oszlop[b], 1);
return kdb[1];
}
void give_initial_chart(int a, int b, vector<int> c, vector<int> d) {
n=a, m=b, k=n*m;
for (int i=0; i<k; i++) sor[i]=c[i], oszlop[i]=d[i], pos[sor[i]*m+oszlop[i]]=i;
for (int i=p; i<2*p; i++) {
int x=i-p;
kezd[i]=x, veg[i]=x, kdb[i]=1;
if (x<k) kert[i]=0;
else kert[i]=p;
}
for (int i=p-1; i>=0; i--) {
int x=2*i, y=2*i+1;
kezd[i]=kezd[x], veg[i]=veg[y];
kert[i]=min(kert[x], kert[y]);
if (kert[x]==kert[i]) kdb[i]+=kdb[x];
if (kert[y]==kert[i]) kdb[i]+=kdb[y];
}
for (int i=0; i<=n; i++) for (int j=0; j<=m; j++) upd(i, j, 1);
}
