#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n, h, w;
vector<int> r, c;
int MxC[4*maxn], MxR[4*maxn], MnC[4*maxn], MnR[4*maxn];
void change(int id, int L, int R, int idx){
if (L+1 == R){
MxR[id] = MnR[id] = r[L];
MxC[id] = MnC[id] = c[L];
return;
}
int mid = (L + R) >> 1;
int lc = 2*id+0, rc = 2*id+1;
if (idx < mid)
change(lc, L, mid, idx);
else
change(rc, mid, R, idx);
MxC[id] = max(MxC[lc], MxC[rc]);
MxR[id] = max(MxR[lc], MxR[rc]);
MnC[id] = min(MnC[lc], MnC[rc]);
MnR[id] = min(MnR[lc], MnR[rc]);
}
inline pair<int,int> merge(pair<int,int> fi, pair<int,int> se){
return {min(fi.first,se.first), max(fi.second,se.second)};
}
pair<pair<int,int>,pair<int,int>> get(int id, int L, int R, int r){
if (R <= r)
return {{MnR[id],MxR[id]},{MnC[id],MxC[id]}};
int mid = (L + R) >> 1;
auto it = get(2*id+0, L, mid, r);
if (mid < r){
auto tmp = get(2*id+1, mid, R, r);
return {merge(it.first,tmp.first), merge(it.second,tmp.second)};
}
return it;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H, w = W, r = R, c = C;
n = h*w;
for (int i = 0; i < n; i++)
change(1, 0, n, i);
}
int isGood(int &r1, int &r2, int &c1, int &c2){
int Size = (r2-r1+1) * (c2-c1+1);
if (Size == n)
return 1;
// cout << r1 << " " << r2 << " " << c1 << " " << c2 << " " << Size << endl;
auto P = get(1, 0, n, Size);
auto it = P.first;
if (it.second > r2)
r2 = it.second;
if (it.first < r1)
r1 = it.first;
it = P.second;
if (it.second > c2)
c2 = it.second;
if (it.first < c1)
c1 = it.first;
// cout << r1 << " " << r2 << " " << c1 << " " << c2 << " " << Size << endl;
if ((r2-r1+1) * (c2-c1+1) != Size)
return isGood(r1, r2, c1, c2);
if (r[Size] < r1)
r1 = r[Size];
if (r[Size] > r2)
r2 = r[Size];
if (c[Size] < c1)
c1 = c[Size];
if (c[Size] > c2)
c2 = c[Size];
return 1 + isGood(r1, r2, c1, c2);
}
int swap_seats(int a, int b){
swap(r[a],r[b]);
swap(c[a],c[b]);
change(1, 0, n, a);
change(1, 0, n, b);
int r1 = r[0], r2 = r[0], c1 = c[0], c2 = c[0], ret = 0;
return isGood(r1, r2, c1, c2);
}
