#include "hpmq.h"
class Data {
friend class Operation;
friend int main();
private:
unsigned int x, sz, T, flag;
void read();
void print() const;
public:
Data() { clr(); }
void add_eq(const Data &a);
void add(const Data &a, const Data &b);
void clr();
bool empty() const;
};
class Operation {
friend int main();
private:
unsigned int a, b, L, R, flag;
void read();
public:
Operation() { clr(); }
void apply(Data &w) const;
void apply(Operation &w) const;
void clr();
bool empty() const;
};
void solve(const int n, const int m, const int p[], const Data d[],
const int x1[], const int x2[], const int y1[], const int y2[],
const Operation o[][3][3], Data ans[][3][3]);
/* END HEADER. */
#include<algorithm>
#include<vector>
int const B=105;
int n,cnt,X1[210],X2[210],Y1[210],Y2[210],X[100010],Y[100010];
Data tr[400010],ans[210][3][3];
Operation lz[400010],op[210][3][3];
int pool[1000010],*pl;
int *son[400010],sons[400010];
struct Vector{
int *bg,len;
void resize(int x,int y){
bg=pl,pl+=x*y,len=y;
for(int i=0;i<x;i++)for(int j=0;j<y;j++)*(bg+i*len+j)=++cnt,sons[cnt]=0;
}
int * operator [](int x){return bg+x*len;}
}vec[810];
std::pair<int,int> dool[400010],*dl;
std::pair<int,int> *x[810],*y[810];
int szx[810],szy[810];
void merge(std::pair<int,int> *a,int la,std::pair<int,int> *b,int lb,std::pair<int,int> *&ans,int &ansl){
ans=dl;
for(int i=0;i<lb;i++){
for(int j=0,l=0,r;j<la;j++,l=r+1){
r=l+a[j].second-a[j].first;
int pl=std::max(l,b[i].first),pr=std::min(r,b[i].second);
if(pl<=pr) *dl++=std::make_pair(a[j].first+pl-l,a[j].second-r+pr);
}
}
ansl=dl-ans;
}
void build(int p,int l,int r){
if(l==r){
vec[p].resize(3,3);
x[p]=dl,dl+=3,y[p]=dl,dl+=3;
x[p][0]=std::make_pair(0,X1[l]-1);
x[p][2]=std::make_pair(X1[l],X2[l]-1);
x[p][1]=std::make_pair(X2[l],n-1);
y[p][0]=std::make_pair(0,Y1[l]-1);
y[p][2]=std::make_pair(Y1[l],Y2[l]-1);
y[p][1]=std::make_pair(Y2[l],n-1);
szx[p]=szy[p]=3;
return;
}
int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
build(ls,l,mid),build(rs,mid+1,r);
merge(x[ls],szx[ls],x[rs],szx[rs],x[p],szx[p]);
merge(y[ls],szy[ls],y[rs],szy[rs],y[p],szy[p]);
vec[p].resize(szx[p],szy[p]);
static int tranx[610],trany[610];
for(int i=0;i<szx[p];i++){
int &k=tranx[i];
for(k=0;k<szx[ls];k++)
if(std::max(x[ls][k].first,x[p][i].first)<=std::min(x[ls][k].second,x[p][i].second))
break;
}
for(int i=0;i<szy[p];i++){
int &k=trany[i];
for(k=0;k<szy[ls];k++)
if(std::max(y[ls][k].first,y[p][i].first)<=std::min(y[ls][k].second,y[p][i].second))
break;
}
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
++sons[vec[ls][tranx[i]][trany[j]]];
for(int i=0;i<szx[ls];i++)
for(int j=0;j<szy[ls];j++)
son[vec[ls][i][j]]=pl,pl+=sons[vec[ls][i][j]],sons[vec[ls][i][j]]=0;
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
son[vec[ls][tranx[i]][trany[j]]][sons[vec[ls][tranx[i]][trany[j]]]++]=vec[p][i][j];
for(int i=0,j=0,g=0,w=0;i<szx[p];i++){
tranx[i]=j;
g+=x[p][i].second-x[p][i].first+1;
if(w+(x[rs][j].second-x[rs][j].first+1)==g)w+=x[rs][j].second-x[rs][j].first+1,++j;
}
for(int i=0,j=0,g=0,w=0;i<szy[p];i++){
trany[i]=j;
g+=y[p][i].second-y[p][i].first+1;
if(w+(y[rs][j].second-y[rs][j].first+1)==g)w+=y[rs][j].second-y[rs][j].first+1,++j;
}
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
++sons[vec[rs][tranx[i]][trany[j]]];
for(int i=0;i<szx[rs];i++)
for(int j=0;j<szy[rs];j++)
son[vec[rs][i][j]]=pl,pl+=sons[vec[rs][i][j]],sons[vec[rs][i][j]]=0;
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
son[vec[rs][tranx[i]][trany[j]]][sons[vec[rs][tranx[i]][trany[j]]]++]=vec[p][i][j];
}
void dfs(int p,int l,int r,int book=1){
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
for(int *u=son[vec[p][i][j]],*ed=u+sons[vec[p][i][j]];u!=ed;++u)
tr[vec[p][i][j]].add_eq(tr[*u]);
if(l==r){
static constexpr int trans[]={0,2,1};
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
ans[l][i][j]=tr[vec[p][trans[i]][trans[j]]];
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
op[l][trans[i]][trans[j]].apply(lz[vec[p][i][j]]);
}else{
int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
dfs(ls,l,mid),dfs(rs,mid+1,r);
}
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
for(int *u=son[vec[p][i][j]],*ed=u+sons[vec[p][i][j]];u!=ed;++u){
if(book) lz[vec[p][i][j]].apply(lz[*u]);
lz[vec[p][i][j]].apply(tr[*u]);
}
}
void solve(int m){
pl=pool,dl=dool;
for(int i=n+1;i<=cnt;i++) tr[i].clr(),lz[i].clr();
cnt=n;
build(1,0,m-1);
static int tranx[100010],trany[100010];
for(int i=0;i<szx[1];i++) for(int j=x[1][i].first;j<=x[1][i].second;j++) tranx[j]=i;
for(int i=0;i<szy[1];i++) for(int j=y[1][i].first;j<=y[1][i].second;j++) trany[j]=i;
for(int i=0;i<n;i++) ++sons[vec[1][tranx[X[i]]][trany[Y[i]]]];
for(int i=0;i<szx[1];i++)
for(int j=0;j<szy[1];j++)
son[vec[1][i][j]]=pl,pl+=sons[vec[1][i][j]],sons[vec[1][i][j]]=0;
for(int i=0;i<n;i++) son[vec[1][tranx[X[i]]][trany[Y[i]]]][sons[vec[1][tranx[X[i]]][trany[Y[i]]]]++]=i;
dfs(1,0,m-1,0);
for(int i=0,p=0;i<szx[1];i++) for(int j=x[1][i].first;j<=x[1][i].second;j++) tranx[j]=p++;
for(int i=0,p=0;i<szy[1];i++) for(int j=y[1][i].first;j<=y[1][i].second;j++) trany[j]=p++;
for(int i=0;i<n;i++) X[i]=tranx[X[i]],Y[i]=trany[Y[i]];
}
void solve(const int n, const int m, const int p[], const Data d[],
const int x1[], const int x2[], const int y1[], const int y2[],
const Operation o[][3][3], Data ans[][3][3]) {
::n=n;
for(int i=0;i<n;i++) tr[i]=d[i],X[i]=i,Y[i]=p[i];
for(int l=0,r;l<m;l=r+1){
r=std::min(l+B,m-1);
for(int i=l;i<=r;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
op[i-l][j][k]=o[i][j][k];
for(int i=l;i<=r;i++) X1[i-l]=x1[i],Y1[i-l]=y1[i],X2[i-l]=x2[i],Y2[i-l]=y2[i];
solve(r-l+1);
for(int i=l;i<=r;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
ans[i][j][k]=::ans[i-l][j][k];
}
}