//gxy001
//TB5x

/* BEGIN HEADER: */
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];
	}
}