class Data{
	friend class Operation;
	friend int main();
  private:
	unsigned int x[2];
	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[2][2];
	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]);


#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=1e5+5,BL=100,M=BL*4+5;
int n;
Data C[N],D[N];
int A[N],B[N],idx[N],idy[N];
int x_1[N],x_2[N],y_1[N],y_2[N];
vector<pair<int,int>>Tx[M],Ty[M];
inline void init(vector<pair<int,int>>&X,int x,int y){
	X.clear(),X.emplace_back(0,x-1),X.emplace_back(y,n-1),X.emplace_back(x,y-1);
}
inline void pushup(vector<pair<int,int>>L,vector<pair<int,int>>R,vector<pair<int,int>>&X){
	vector<pair<int,int>>Y=R,Z;
	sort(Y.begin(),Y.end());
	int p=0,q=-1;
	for(auto [l,r]:Y){
		for(;p<L.size()&&q+L[p].second-L[p].first+1<=r;++p)
			q+=L[p].second-L[p].first+1,Z.emplace_back(L[p]);
		if(q<r)Z.emplace_back(L[p].first,L[p].first+r-q-1),L[p].first+=r-q,q=r;
	}
	vector<int>pre(Z.size()+1);
	for(int i=0;i<Z.size();++i)pre[i+1]=pre[i]+Z[i].second-Z[i].first+1;
	X.clear();
	for(auto [l,r]:R){
		l=lower_bound(pre.begin(),pre.end(),l)-pre.begin();
		r=lower_bound(pre.begin(),pre.end(),r+1)-pre.begin()-1;
		for(int i=l;i<=r;++i)X.emplace_back(Z[i]);
	}
}
inline void build(int p,int l,int r){
	if(l==r){
		init(Tx[p],x_1[l],x_2[l]);
		init(Ty[p],y_1[l],y_2[l]);
		return;
	}
	const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(Tx[ls],Tx[rs],Tx[p]);
	pushup(Ty[ls],Ty[rs],Ty[p]);
}
inline vector<vector<Data>>reduce(vector<pair<int,int>>X,vector<pair<int,int>>nX,vector<pair<int,int>>Y,vector<pair<int,int>>nY,vector<vector<Data>>A){
	vector<vector<Data>>B(nX.size(),vector<Data>(nY.size()*2));
	sort(nX.begin(),nX.end()),sort(nY.begin(),nY.end());
	for(auto&[l,r]:nX)
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
	for(auto&[l,r]:nY)
		l=lower_bound(Y.begin(),Y.end(),make_pair(l,-1))-Y.begin(),
		r=lower_bound(Y.begin(),Y.end(),make_pair(r+1,-1))-Y.begin()-1;
	for(int i=0;i<nX.size();++i)
		for(int k=nX[i].first;k<=nX[i].second;++k)
			for(int j=0;j<nY.size();++j)
				for(int l=nY[j].first;l<=nY[j].second;++l)
					B[i][j].add_eq(A[k][l]);
	return B;
}
inline void increase(vector<pair<int,int>>X,vector<pair<int,int>>nX,vector<pair<int,int>>Y,vector<pair<int,int>>nY,vector<vector<Operation>>&W,vector<vector<Data>>&A){
	vector<vector<Data>>B(X.size(),vector<Data>(Y.size()*2));
	vector<vector<Operation>>C(X.size(),vector<Operation>(Y.size()));
	for(auto&[l,r]:nX)
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
	for(auto&[l,r]:nY)
		l=lower_bound(Y.begin(),Y.end(),make_pair(l,-1))-Y.begin(),
		r=lower_bound(Y.begin(),Y.end(),make_pair(r+1,-1))-Y.begin()-1;
	for(int i=0,p=0;i<nX.size();++i)
		for(int k=nX[i].first;k<=nX[i].second;++k,++p)
			for(int j=0,q=0;j<nY.size();++j)
				for(int l=nY[j].first;l<=nY[j].second;++l,++q)
					B[p][q]=A[k][l],C[p][q]=W[i][j];
	A=B,W=C;
}
inline void increase(vector<pair<int,int>>X,vector<pair<int,int>>nX,vector<pair<int,int>>Y,vector<pair<int,int>>nY,vector<vector<Operation>>&W){
	vector<vector<Operation>>C(X.size(),vector<Operation>(Y.size()));
	for(auto&[l,r]:nX)
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
	for(auto&[l,r]:nY)
		l=lower_bound(Y.begin(),Y.end(),make_pair(l,-1))-Y.begin(),
		r=lower_bound(Y.begin(),Y.end(),make_pair(r+1,-1))-Y.begin()-1;
	for(int i=0,p=0;i<nX.size();++i)
		for(int k=nX[i].first;k<=nX[i].second;++k,++p)
			for(int j=0,q=0;j<nY.size();++j)
				for(int l=nY[j].first;l<=nY[j].second;++l,++q)
					C[p][q]=W[k][l];
	W=C;
}
inline vector<pair<int,int>>update(vector<pair<int,int>>X,vector<pair<int,int>>nX){
	vector<pair<int,int>>Z;
	for(auto&[l,r]:nX){
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
		for(int i=l;i<=r;++i)Z.emplace_back(X[i]);
	}
	int p=0;
	for(auto&[l,r]:Z){
		int nl=p,nr=p+r-l;
		p+=r-l+1;
		l=nl,r=nr;
	}
	return Z;
}
inline vector<vector<Operation>>solve(int p,int l,int r,vector<vector<Data>>A,const Operation o[][3][3],Data ans[][3][3]){
	if(l==r){
		for(int i=0;i<3;++i)for(int j=0;j<3;++j)ans[l][i][j]=A[i][j];
		vector<vector<Operation>>W(3,vector<Operation>(3));
		for(int i=0;i<3;++i)for(int j=0;j<3;++j)W[(3-i)%3][(3-j)%3]=o[l][i][j];
		return W;
	}
	const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
	vector<pair<int,int>>X=Tx[p],Y=Ty[p];
	sort(X.begin(),X.end()),sort(Y.begin(),Y.end());
	vector<vector<Operation>>LsW=solve(ls,l,mid,reduce(X,Tx[ls],Y,Ty[ls],A),o,ans);
	increase(X,Tx[ls],Y,Ty[ls],LsW,A);
	for(int i=0;i<Tx[p].size();++i)
		for(int j=0;j<Ty[p].size();++j)
			LsW[i][j].apply(A[i][j]);
	X=update(X,Tx[ls]),Y=update(Y,Ty[ls]);
	vector<vector<Operation>>RsW=solve(rs,mid+1,r,reduce(X,Tx[rs],Y,Ty[rs],A),o,ans);
	increase(X,Tx[rs],Y,Ty[rs],RsW,A);
	increase(X,Tx[rs],Y,Ty[rs],LsW);
	for(int i=0;i<Tx[p].size();++i)
		for(int j=0;j<Ty[p].size();++j)
			RsW[i][j].apply(LsW[i][j]);
	return LsW;
}
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;
	copy_n(p,n,A),copy_n(d,n,C);
	copy_n(x1,m,x_1),copy_n(x2,m,x_2),copy_n(y1,m,y_1),copy_n(y2,m,y_2);
	for(int i=0;i<m;++i)assert(0<x1[i]&&x1[i]<x2[i]&&x2[i]<n&&0<y1[i]&&y1[i]<y2[i]&&y2[i]<n);
	for(int l=0,r=BL-1;l<m;l+=BL,r+=BL){
		build(1,l,min(r,m-1));
		auto X=Tx[1],Y=Ty[1];sort(X.begin(),X.end()),sort(Y.begin(),Y.end());
		for(int i=0;i<X.size();++i)for(int j=X[i].first;j<=X[i].second;++j)idx[j]=i;
		for(int i=0;i<Y.size();++i)for(int j=Y[i].first;j<=Y[i].second;++j)idy[j]=i;
		vector<vector<Data>>S(X.size(),vector<Data>(Y.size()*2));
		for(int i=0;i<n;++i)S[idx[i]][idy[A[i]]].add_eq(C[i]);
		vector<vector<Operation>>W=solve(1,l,min(r,m-1),S,o,ans);
		for(int i=0;i<Tx[1].size();++i)for(int j=Tx[1][i].first;j<=Tx[1][i].second;++j)idx[j]=i;
		for(int i=0;i<Ty[1].size();++i)for(int j=Ty[1][i].first;j<=Ty[1][i].second;++j)idy[j]=i;
		for(int i=0;i<n;++i)W[idx[i]][idy[A[i]]].apply(C[i]);
		int p=0;for(auto [x,y]:Tx[1])for(int i=x;i<=y;++i)idx[i]=p++;
		int q=0;for(auto [x,y]:Ty[1])for(int i=x;i<=y;++i)idy[i]=q++;
		for(int i=0;i<n;++i)B[idx[i]]=idy[A[i]],D[idx[i]]=C[i];
		copy_n(B,n,A),copy_n(D,n,C);
	}
}