#include<bits/stdc++.h>
//=========================================================
typedef long long ll;
//typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
#define pd push_back
#define all(x) x.begin(),x.end()
#define allA(x,l,r) x+l,x+r+1
#define mpr std::make_pair
#define ve std::vector
#define mpre(v) v.insert(v.begin(),0)
#define lb lower_bound
//=========================================================
namespace Balance_tree{
	struct Mes{
		Mes(){}
		friend Mes operator + (Mes A,Mes B){
			Mes ans;
			return ans;
		}
	};
	const int N=2e5+10;
	std::mt19937 rnd(time(NULL));
	struct Mes_BLT{
		struct node{int l,r;ll val;int key,sz;Mes rv,v;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;
			if(tr[rt].l&&tr[rt].r)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v+tr[tr[rt].r].rv;
			else if(tr[rt].l)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v;
			else if(tr[rt].r)tr[rt].rv=tr[rt].v+tr[tr[rt].r].v;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,ll val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(int val,Mes P){int id=newid();return tr[id]={0,0,val,int(rnd()),1,P,P},id;}
		void insert(ll val,Mes P){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val,P)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}Mes query(ll l,ll r){
			int x,y,z;split(rot,r,x,z);
			split(x,l-1,x,y);
			Mes ans=tr[y].rv;
			rot=merge(merge(x,y),z);
			return ans;
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0,Mes(),Mes()};cnt=rot=0;bin.clear();}
	};
	struct Basic_BLT{
		struct node{int l,r;ll val;int key,sz;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,int val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(ll val){int id=newid();return tr[id]={0,0,val,int(rnd()),1},id;}
		void insert(ll val){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}int Get_rank(int rt,int k){
			if(k<=tr[tr[rt].l].sz)return Get_rank(tr[rt].l,k);
			if(k==tr[tr[rt].l].sz+1)return rt;
			return Get_rank(tr[rt].r,k-tr[tr[rt].l].sz-1);
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0};cnt=rot=0;bin.clear();}
	};
}
namespace segment_tree{
	const int N=2e5+10;
	template<typename M,typename T> struct sg_tree{
		struct node{M Mes;T Tag;int l,r;}tr[5];
		int rot;int cnt;
		void init(){for(int i=1;i<=cnt;i++)tr[i].Mes=M(),tr[i].Tag=T(),tr[i].l=tr[i].r=0;rot=cnt=0;}
		void pushup(int rt){
			tr[rt].Mes=M();
			if(tr[rt].l&&tr[rt].r)tr[rt].Mes=tr[tr[rt].l].Mes+tr[tr[rt].r].Mes;
			else if(tr[rt].l)tr[rt].Mes=tr[tr[rt].l].Mes;
			else if(tr[rt].r)tr[rt].Mes=tr[tr[rt].r].Mes;
		}
		void addson(int rt,T x){tr[rt].Mes=tr[rt].Mes+x;tr[rt].Tag=tr[rt].Tag+x;}
		void pushdown(int rt){
			if(tr[rt].Tag==T())return;
			if(tr[rt].l)addson(tr[rt].l,tr[rt].Tag);
			if(tr[rt].r)addson(tr[rt].r,tr[rt].Tag);
			tr[rt].Tag=T();
		}
		void build(int &rt,int l,int r,std::vector<M> &A){
			if(!rt)rt=++cnt;
			if(l==r)return tr[rt].Mes=A[l],void();
			auto mid=l+r>>1;
			build(tr[rt].l,l,mid,A);build(tr[rt].r,mid+1,r,A);
			pushup(rt);
		}
		void change_Seq(int &rt,int l,int r,int x,int y,T P){
			if(x>y)return;
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(x<=l&&r<=y)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid)change_Seq(tr[rt].l,l,mid,x,y,P);
			if(y>mid)change_Seq(tr[rt].r,mid+1,r,x,y,P);
			pushup(rt);
		}
		void change_p(int &rt,int l,int r,int x,T P){
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(l==r)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			(x<=mid)?change_p(tr[rt].l,l,mid,x,P):change_p(tr[rt].r,mid+1,r,x,P);
			pushup(rt);
		}
		M query(int rt,int l,int r,int x,int y){
			if(!rt||x>y)return M();
			if(x<=l&&r<=y)return tr[rt].Mes;
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid&&y>mid)return query(tr[rt].l,l,mid,x,y)+query(tr[rt].r,mid+1,r,x,y);
			if(x<=mid)return query(tr[rt].l,l,mid,x,y);
			if(y>mid)return query(tr[rt].r,mid+1,r,x,y);
			assert(false);
		}
		void build(int l,int r,std::vector<M> &A){build(rot,l,r,A);}
		void change_Seq(int l,int r,int x,int y,T P){
			change_Seq(rot,l,r,x,y,P);}
		void change_p(int l,int r,int x,T P){
			change_p(rot,l,r,x,P);}
		M query(int l,int r,int x,int y){
			return query(rot,l,r,x,y);}
	};
	struct Mes{
		Mes(){}
		Mes(ll _S,int _l,int _r){}
		Mes operator + (Mes P){
			Mes ans=Mes();
			return ans;
		}
	};
	struct Tag{
		Tag(){}
		Tag operator + (Tag P){
			Tag ans=Tag();
			return ans;
		}
		bool operator == (Tag P){return true!=false;}
	};
	Mes operator + (Mes A,Tag B){return A;}
}
namespace Fenwick_Tree{
	const int N=2e5+10;
	struct FwT{
		ll tr[5];int u;
		void init(int _u){
			u=_u;
			for(int i=0;i<=u;i++)tr[i]=0;}
		void add(int x,ll y){for(;x<=u;x+=(x&-x))tr[x]+=y;}
		ll query(int x){ll ans=0;for(;x;x^=(x&-x))ans+=tr[x];return ans;}
		ll query(int l,int r){if(l>r)return 0;return query(r)-query(l-1);}
	};
}
//=========================================================
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll QA(ll x,ll y,ll mod){ll ans=0;for(;y;y>>=1,x=(x<<1)%mod)if(y&1)ans=(ans+x)%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
typedef unsigned U;
const int M=998244353;
struct ModInt{
	static constexpr U mod=M;
	U val;
	constexpr ModInt():val(0U){}
	constexpr ModInt(U _val):val(_val){}
	constexpr ModInt(int _val):val((_val%int(mod)+int(mod))%int(mod)){}
	constexpr ModInt(ll _val):val((_val%ll(mod)+ll(mod))%ll(mod)){}
	ModInt(const ModInt &P):val(P.val){}
	inline ModInt operator +(ModInt p){return ModInt(int(val)+int(p.val));}
	inline ModInt operator -(ModInt p){return ModInt(int(val)-int(p.val));}
	inline ModInt operator *(ModInt p){return ModInt(1ll*val*p.val);}
	inline ModInt QP(ll y){
		if(y<0)return inv().QP(-y);
		ModInt A=(*this),B=1U;
		for(;y;A=A*A,y>>=1)if(y&1)B=B*A;
		return B;
	}inline ModInt inv(){return QP(mod-2);}
	inline ModInt operator /(ModInt p){return (*this)*p.inv();}
	inline ModInt operator ^(ModInt p){return QP(p.val);}
	template<typename T>
	inline ModInt operator ^(T p){return QP(p);}

	template<typename T>
	inline ModInt operator +(T p){return (*this)+ModInt(p);}
	template<typename T>
	inline ModInt operator -(T p){return (*this)-ModInt(p);}
	template<typename T>
	inline ModInt operator *(T p){return (*this)*ModInt(p);}
	template<typename T>
	inline ModInt operator /(T p){return (*this)/ModInt(p);}

	inline ModInt operator +(){return (*this);}
	inline ModInt operator -(){return ModInt(0)-(*this);}

	template<typename T>
	inline friend ModInt operator +(T A,ModInt P){return ModInt(A)+P;}
	template<typename T>
	inline friend ModInt operator -(T A,ModInt P){return ModInt(A)-P;}
	template<typename T>
	inline friend ModInt operator *(T A,ModInt P){return ModInt(A)*P;}
	template<typename T>
	inline friend ModInt operator /(T A,ModInt P){return ModInt(A)/P;}

	inline void operator --(){val=(!val?mod-1:val-1);}
	inline void operator ++(){val=(val==mod-1?0:val+1);}

	inline void operator +=(ModInt P){(*this)=(*this)+P;}
	inline void operator -=(ModInt P){(*this)=(*this)-P;}
	inline void operator *=(ModInt P){(*this)=(*this)*P;}
	inline void operator /=(ModInt P){(*this)=(*this)/P;}

	template<typename T>
	inline void operator +=(T P){return (*this)=(*this)+ModInt(P);}
	template<typename T>
	inline void operator -=(T P){return (*this)=(*this)-ModInt(P);}
	template<typename T>
	inline void operator *=(T P){return (*this)=(*this)*ModInt(P);}
	template<typename T>
	inline void operator /=(T P){return (*this)=(*this)/ModInt(P);}
	template<typename T>
	inline void operator ^=(T P){return (*this)=(*this)^P;}

	U key(){return val;}
	inline bool operator == (ModInt P){return P.val==val;}
	inline bool operator != (ModInt P){return !((*this)==P);}

};
//=========================================================
namespace IO{
	const double eps=1e-8;
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char tmp[BUFSIZE];int cnt=0;
	inline char getch(){if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);return is==it?EOF:*is++;}
	int readInt(){int x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	ll readLL(){ll x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
//	Int readInt128(){Int x=0;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	char readChar(){char c=0;while(!c||c==' '||c=='\n')c=getch();return c;}
	std::string readString(){std::string S;char c=0;while(!c||c==' '||c=='\n')c=getch();while(c!=' '&&c!='\n')S.pd(c),c=getch();return S;}
	LD readDouble(){LD x=0,d=1;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();int cnt=0;bool flg=false;while(isdigit(c)){
		x=x*10+(c^48),flg|=(c^48),cnt+=flg,c=getch();if(cnt>=12)goto flg;}if(c=='.'){c=getch();while(isdigit(c)){d*=10,x+=(c^48)/d;flg|=(c^48),cnt+=flg;
		if(cnt>=12)goto flg;c=getch();}}flg:;return !y?x:-x;}
	ul readUll(){ul x=0;char c=0;while(!isdigit(c))c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return x;}

	void flush(){fwrite(tmp,1,cnt,stdout);cnt=0;}
	void putch(char c){tmp[cnt++]=c;if(cnt==BUFSIZE)flush();}
	void putint(int x){char Q[10];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
//	void putInt128(Int x){char Q[45];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putLL(ll x){char Q[20];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putString(std::string x){for(auto p:x)putch(p);}
	void putDouble(LD x){if(x<0)x=-x,putch('-');if(fabs(x)<=eps)return putch(0);bool flg=false;LD d=1e10;LD l=std::min(LD(1e-10),1.0/std::max(LD(1),x));
		while(d>=l){if(d<=1){if(ll(x/d+d*1e-2)%10>0||flg)putch(ll(x/d+d*1e-2)%10+'0'),flg=true;}else{if(ll(x/d)%10>0||flg)putch(ll(x/d)%10+'0'),flg=true;
		}x-=ll(x/d+eps)*d; if(d==1){if(!flg)putch('0');putch('.');}d/=10;}}
	void putUll(ul x){char Q[25];int tp=0;if(!x)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}

	struct Basic{
		Basic &operator>>(int &A){A=IO::readInt();return (*this);}
		Basic &operator>>(ll &A){A=IO::readLL();return (*this);}
//		Basic &operator>>(Int &A){A=IO::readInt128();return (*this);}
		Basic &operator>>(char &A){A=IO::readChar();return (*this);}
		Basic &operator>>(std::string &A){A=IO::readString();return (*this);}
		Basic &operator>>(double &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(LD &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(float &A){A=IO::readDouble();return (*this);}
		template<typename T1,typename T2>
		Basic &operator>>(std::pair<T1,T2>&v){(*this)>>v.first>>v.second;return (*this);}
		template<typename T,int d>
		Basic &operator>>(std::array<T,d> &v){for(auto &p:v)(*this)>>p;return (*this);}
		template<typename T>
		Basic &operator>>(std::vector<T> &v){for(auto &p:v)(*this)>>p;return (*this);}
		Basic &operator>>(ul &v){v=readUll();return (*this);}

		Basic &operator<<(const int &A){putint(A);return (*this);}
		Basic &operator<<(const char &A){putch(A);return (*this);}
		Basic &operator<<(const ll &A){putLL(A);return (*this);}
//		Basic &operator<<(const Int &A){putInt128(A);return (*this);}
		Basic &operator<<(const std::string &A){putString(A);return (*this);}
		Basic &operator<<(const LD &A){putDouble(A);return (*this);}
		Basic &operator<<(const double &A){putDouble(A);return (*this);}
		Basic &operator<<(const float &A){putDouble(A);return (*this);}
		template<typename T>
		Basic &operator<<(const std::vector<T> &v){for(int i=0;i<v.size();i++)(*this)<<v[i]<<(v.size()==i+1?'\n':' ');return (*this);}
		Basic &operator<<(const ul &A){putUll(A);return (*this);}

		void Flush(){flush();}
	}cin,cout;
}
//=========================================================
namespace Grader{
	std::vector<int>S;
	void Get(std::vector<int>v){
		assert(S.empty());

		reverse(all(S));
	}
	int readInt(){
		assert(!S.empty());
		int x=S.back();
		S.pop_back();
		return x;
	}
	void putInt(int x){
		std::vector<int>P;
		P.pd(x);Get(P);
	}void putVec(std::vector<int>v){Get(v);}
}
//=========================================================
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
//=========================================================
//const int mod=998244353;
//int add(int x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}
//int mul(int x,int y){return 1ll*x*y%mod;}
//void add(int &x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;}
const int N=2e5+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct costDinic{
	struct node{int y,nxt;ll val,c;}E[N<<1];
	int H[N],cnt;
	void add(int x,int y,ll z,ll c){E[++cnt]={y,H[x],z,c};H[x]=cnt;}
	void Add(int x,int y,ll z,ll c){add(x,y,z,c);add(y,x,0,-c);}
	int dep[N],cur[N];ll dis[N];
	int S,T,n;ll C;
	bool vis[N];
	void init(int _S,int _T,int _n){
		S=_S;T=_T;n=_n;
		for(int i=1;i<=n;i++)H[i]=0;
		cnt=1;C=0;
		memset(vis,0,sizeof(vis));
	}
	bool SPFA(){
		memset(dis,0x3f,sizeof(dis));
		std::queue<int>q;q.push(S);
		dis[S]=0;vis[S]=true;
		while(!q.empty()){
			auto x=q.front();q.pop();vis[x]=false;
			for(int i=H[x];i;i=E[i].nxt){
				auto y=E[i].y;
				if(E[i].val&&dis[x]+E[i].c<dis[y]){
					dis[y]=dis[x]+E[i].c;
					if(!vis[y])q.push(y),vis[y]=true;
				}
			}
		}return dis[T]!=inf;
	}
	ll dfs(int x,ll mf){
		if(x==T)return mf;ll ans=0;vis[x]=true;
		for(int &i=cur[x];i&&ans<mf;i=E[i].nxt){
			auto y=E[i].y;
			if(!vis[y]&&E[i].val&&dis[y]==dis[x]+E[i].c){
				ll f=dfs(y,std::min(E[i].val,mf-ans));
				if(f)C+=f*E[i].c,E[i].val-=f,E[i^1].val+=f,ans+=f;
			}
		}vis[x]=false;
		return ans;
	}
	std::pair<ll,ll>Dinic(){
		C=0;
		ll ans=0,x;
		while(SPFA()){
			memcpy(cur,H,sizeof(cur));
			while(x=dfs(S,inf))ans+=x;
		}
	//	IO::cout<<ans<<' '<<C<<'\n';
		return mpr(ans,C);
	}
}E;
void solve(){
	//don't forget to open long long
	int S,T,T0;
	int n,m,D;IO::cin>>n>>m>>D;
	ve<ve<int>>v1(n+1,ve<int>(m+1)),v2(n+1,ve<int>(m+1));
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			IO::cin>>v1[i][j];
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			IO::cin>>v2[i][j];
	auto to=[&](int i,int j)->int{return (i-1)*(m-1)+j;};
	E.init(S=to(n-1,m-1)+1,T0=to(n-1,m-1)+3,(n-1)*(m-1)+3);
	T=to(n-1,m-1)+2;
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++){
		//	IO::cout<<to(i,j)<<' '<<to(i+1,j)<<' '<<to(i,j+1)<<'\n';
			if(i+1<n)E.Add(to(i+1,j),to(i,j),v1[i+1][j],0),
				E.Add(to(i,j),to(i+1,j),v1[i+1][j],0);
		//	if(i+1<n)IO::cout<<v1[i+1][j]<<' ';
			if(j+1<m)E.Add(to(i,j+1),to(i,j),v2[i][j+1],0),
				E.Add(to(i,j),to(i,j+1),v2[i][j+1],0);
		//	if(j+1<m)IO::cout<<v2[i][j+1]<<' ';
		//	IO::cout<<'\n';
		}
	for(int i=1;i<m;i++)
		E.Add(to(1,i),T,v1[1][i],0),
		E.Add(S,to(n-1,i),v1[n][i],0);
	E.Add(T,T0,inf,0);
	E.Dinic();
	for(int i=E.H[T0];i;i=E.E[i].nxt){
		E.E[i].val=0;
		E.E[i^1].val=0;
	}
	E.Add(T,T0,D,0);
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++){
			if(i+1<n)E.Add(to(i+1,j),to(i,j),inf,1),
				E.Add(to(i,j),to(i+1,j),inf,1);
			if(j+1<m)E.Add(to(i,j+1),to(i,j),inf,1),
				E.Add(to(i,j),to(i,j+1),inf,1); 
		}
	for(int i=1;i<m;i++)
		E.Add(to(1,i),T,inf,1),
		E.Add(S,to(n-1,i),inf,1);
	ll VAL=E.Dinic().second;
	IO::cout<<VAL<<'\n';
	auto rec=[&](int x)->std::pair<int,int>{return {(x-1)/(m-1)+1,(x-1)%(m-1)+1};};
	for(int V=1;V<=(n-1)*(m-1)+1;V++){
		for(int i=E.H[V];i;i=E.E[i].nxt){
			int y=E.E[i].y;
			if(E.E[i].c<=0)continue;
			int d=E.E[i^1].val;
			if(y==T)v1[1][rec(V).second]+=d;
			else if(V==S)v1[n][rec(y).second]+=d;
			else if(rec(V).first!=rec(y).first)
				v1[std::min(rec(V).first,rec(y).second)][rec(V).second]+=d;
			else v2[rec(V).first][std::min(rec(V).second,rec(y).second)]+=d;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			IO::cout<<v1[i][j]<<(j+1==m?'\n':' ');
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			IO::cout<<v2[i][j]<<(j==m?'\n':' ');
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	//std::ios::sync_with_stdio(false);
	//std::cin.tie(0);
	//std::cout.tie(0);
	int T=1;IO::cin>>T;
	while(T--)solve();
	IO::cout.Flush();
	return 0;
}