QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288988#6325. Peaceful ResultsqLAC ✓382ms69156kbC++1415.7kb2023-12-23 14:39:052023-12-23 14:39:06

Judging History

你现在查看的是最新测评结果

  • [2023-12-23 14:39:06]
  • 评测
  • 测评结果:AC
  • 用时:382ms
  • 内存:69156kb
  • [2023-12-23 14:39:05]
  • 提交

answer

#include<cstdio>
#include<type_traits>
#include<initializer_list>
#include<memory>
/**
 * Author: Cracker
 * Version: 0x04
 * Warning:
 * 	Vector is slower than in STL.
 * 	Static Allocator may lead to RE.
 * 	Turn to C++17.
*/
namespace Default_Source{
	namespace{
		using ll=long long;
		using uint=unsigned;
		using ull=unsigned long long;
	}
	namespace Memory{
		struct Memory_Pool_Base{
			template<typename _Tp>
			_Tp*allocate(){return new _Tp[1]{};}
			template<typename _Tp>
			_Tp*allocate(std::size_t n){return new _Tp[n]{};}
			template<typename _Tp>
			void deallocate(_Tp*v){delete[] v;}
		};
		Memory_Pool_Base Runtime_Memory_Pool;
		template<typename _Tp>
		struct Allocator_Base{
			using value_type=_Tp;
			template<typename T>
			struct rebind{using other=Allocator_Base<T>;};
			_Tp*allocate(){return Runtime_Memory_Pool.allocate<_Tp>();}
			_Tp*allocate(std::size_t n){return Runtime_Memory_Pool.allocate<_Tp>(n);}
			void deallocate(_Tp*v,std::size_t n){Runtime_Memory_Pool.deallocate<_Tp>(v);}
		    template<typename T,typename ...Args>
			void construct(T*p,Args&&... args){new(p)T(std::forward<Args>(args)...);}
			template<typename T>
			void destroy(T*p){p->~T();}
		};
		template<typename _Tp,std::size_t MAX_SIZE>
		class Static_Allocator_Base{
		private:
			_Tp pool[MAX_SIZE],*cur=pool;
		public:
			using value_type=_Tp;
			template<typename T>
			struct rebind{using other=Static_Allocator_Base<T,MAX_SIZE>;};
			_Tp*allocate(){return cur++;}
			_Tp*allocate(std::size_t n){
				static _Tp*tmp;
				tmp=cur,cur+=sizeof(_Tp)*n;
				return tmp;
			}
			void deallocate(_Tp*v,std::size_t n){}
		    template<typename T,typename ...Args>
			void construct(T*p,Args&&...args){new(p)T(std::forward<Args>(args)...);}
			template<typename T>
			void destroy(T*p){p->~T();}
		};
	}
	namespace Container{
		template<typename _Tp,typename _Allocator=std::allocator<int>>
		class vector{
		private:
			_Tp*arr;
			int cur;
			static _Allocator Allocator;
			void extend(std::size_t before,std::size_t after){
				_Tp*_arr=Allocator.allocate(after);
				__builtin_memcpy(_arr,arr,sizeof(_Tp)*before);
				Allocator.deallocate(arr,before),arr=_arr;
			}
			void shrink(std::size_t before,std::size_t after){
				_Tp*_arr=Allocator.allocate(after);
				__builtin_memcpy(_arr,arr,sizeof(_Tp)*after);
				Allocator.deallocate(arr,before),arr=_arr;
			}
		public:
			vector():arr{Allocator.allocate(0)},cur{0}{}
			auto begin(){return arr;}
			auto end(){return arr+cur;}
			_Tp&operator[](int x){return arr[x];}
			_Tp operator[](int x)const{return arr[x];}
			std::size_t size()const{return cur;}
			template<typename T>
			void push_back(T&&x){
				if((cur&(-cur))==cur) extend(cur,cur<<1);
				arr[cur++]=x;
			}
		};
		template<typename _Tp,typename _Allocator>
		_Allocator vector<_Tp,_Allocator>::Allocator;
	}
	namespace IO{
		namespace Flush{
			struct Flush_Base{};
			struct Input_Flush_Base:Flush_Base{char getc(){return getchar();}};
			template<std::size_t BUFSIZE>
			class Fast_Input_Flush_Base:Input_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur=buf;
			public:
				Fast_Input_Flush_Base(){std::fread(buf,1,BUFSIZE,stdin);}
				char getc(){return*cur++;}
			};
			template<std::size_t BUFSIZE>
			class Fast_Input_Flush_Safer:Input_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur,*nil;
				bool reload(){return (nil=(cur=buf)+std::fread(buf,1,BUFSIZE,stdin))!=buf;}
			public:
				Fast_Input_Flush_Safer(){reload();}
				char getc(){return (cur!=nil||reload())?*cur++:EOF;}
			};
			struct Output_Flush_Base:Flush_Base{void putc(char ch){putchar(ch);}};
			template<std::size_t BUFSIZE>
			class Fast_Output_Flush_Base:Output_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur=buf;
			public:
				~Fast_Output_Flush_Base(){std::fwrite(buf,1,cur-buf,stdout);}
				void putc(char ch){*cur++=ch;}
			};
		}
		template<typename _Input_Flush=Flush::Input_Flush_Base>
		class Fast_InStream{
			static_assert(std::is_base_of<Flush::Input_Flush_Base,_Input_Flush>::value);
			static _Input_Flush Input;
			using List_Out=std::initializer_list<int>;
		public:
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type uread(_Tp&x){
				x=0;char Ch=Input.getc();
				for(;Ch<'0'||Ch>'9';Ch=Input.getc());
				for(;Ch>='0'&&Ch<='9';Ch=Input.getc()) x=x*10+(Ch&15);
			}
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type read(_Tp&x){
				x=0;bool sign=false;char Ch=Input.getc();
				for(;Ch<'0'||Ch>'9';Ch=Input.getc()) if(Ch=='-') sign=true;
				for(;Ch>='0'&&Ch<='9';Ch=Input.getc()) x=x*10+(sign?-(Ch&15):(Ch&15));
			}
			void read(char*str){
				while((*str=Input.getc())==' '||*str=='\n');
				while((*++str=Input.getc())!=' '&&*str!='\n');
				*str='\0';
			}
			template<typename ...Args>
			void read(Args&&...args){void(List_Out{(read(args),0)...});}
			template<typename T>
			T read(){
				static T x;
				return read(x),x;
			}
		};
		template<typename _Input_Flush>
		_Input_Flush Fast_InStream<_Input_Flush>::Input;
		template<typename _Output_Flush=Flush::Output_Flush_Base>
		class Fast_OutStream{
			static_assert(std::is_base_of<Flush::Output_Flush_Base,_Output_Flush>::value);
			static _Output_Flush Output;
			using List_Out=std::initializer_list<int>;
		public:
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type write(_Tp x){
				static char sta[114];
				int top=0;
				if(x<0){
					Output.putc('-');
					do sta[top++]=(-(x%10))|48,x/=10;
					while(x);
				}
				else
					do sta[top++]=(x%10)|48,x/=10;
					while(x);
				while(top) Output.putc(sta[--top]);
			}
			void write(char Ch){Output.putc(Ch);}
			void write(const char*Str){while(*Str) Output.putc(*Str++);}
			void write(char*Str){write(static_cast<const char*>(Str));}
			template<typename ...Args>
			void write(Args...args){void(List_Out{(write(args),0)...});}
			template<typename ...Args>
			void writeln(Args...args){write(args...),Output.putc('\n');}
		};
		template<typename _Output_Flush>
		_Output_Flush Fast_OutStream<_Output_Flush>::Output;
	}
	namespace DS{
		namespace Sgt{
			enum SegmentTree_Type{Single=1,Interval=2};
			template<typename Info,SegmentTree_Type _Modify,SegmentTree_Type _Query,typename _Allocator=Memory::Allocator_Base<Info>>
			class SegmentTree{};
			template<typename Info,typename _Allocator>
			class SegmentTree<Info,Interval,Interval,_Allocator>{
			private:
				static _Allocator allocator;
				int n;
				Info*tr;
				void build(int p,int l,int r){
					if(l==r) return tr[p].init(l);
					int mid=(l+r)>>1;
					build(p<<1,l,mid),build(p<<1|1,mid+1,r);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				void modify(int p,int l,int r,int L,int R,const Info&V){
					if(L<=l&&r<=R) return tr[p].get(V);
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					if(L<=mid) modify(p,l,mid,L,R,V);
					if(R>mid) modify(p<<1|1,mid+1,r,L,R,V);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				Info query(int p,int l,int r,int L,int R){
					if(L<=l&&r<=R) return tr[p].info;
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					if(L<=mid&&R>mid) return merge(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
					else return L<=mid?query(p<<1,l,mid,L,R):query(p<<1|1,mid+1,r,L,R);
				}
			public:
				SegmentTree():n{}{tr=allocator.allocate(0);}
				void resize(int _n){allocator.deallocate(tr,n),tr=allocator.allocate((n=_n)<<2);}
				~SegmentTree(){allocator.deallocate(tr,n);}
				void build(){build(1,1,n);}
				void build(int _n){resize(_n),build(1,1,n);}
				void modify(int L,int R,const Info&V){modify(1,1,n,L,R,V);}
				Info query(int L,int R){return query(1,1,n,L,R);}
			};
			template<typename Info,typename _Allocator>
			_Allocator SegmentTree<Info,Interval,Interval,_Allocator>::allocator;
			template<typename Info,typename _Allocator>
			class SegmentTree<Info,Interval,Single,_Allocator>{
			private:
				static _Allocator allocator;
				int n;
				Info*tr;
				void build(int p,int l,int r){
					if(l==r) return tr[p].init(l);
					int mid=(l+r)>>1;
					build(p<<1,l,mid),build(p<<1|1,mid+1,r);
				}
				void modify(int p,int l,int r,int L,int R,const Info&V){
					if(L<=l&&r<=R) return tr[p].get(V);
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					if(L<=mid) modify(p<<1,l,mid,L,R,V);
					if(R>mid) modify(p<<1|1,mid+1,r,L,R,V);
				}
				Info query(int p,int l,int r,int X){
					if(l==r) return tr[p];
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					return X<=mid?query(p<<1,l,mid,X):query(p<<1|1,mid+1,r,X);
				}
			public:
				SegmentTree():n{}{tr=allocator.allocate(0);}
				void resize(int _n){allocator.deallocate(tr,n),tr=allocator.allocate((n=_n)<<2);}
				~SegmentTree(){allocator.deallocate(tr,n);}
				void build(){build(1,1,n);}
				void build(int _n){resize(_n),build(1,1,n);}
				void modify(int L,int R,const Info&V){modify(1,1,n,L,R,V);}
				Info query(int X){return query(1,1,n,X);}
			};
			template<typename Info,typename _Allocator>
			_Allocator SegmentTree<Info,Interval,Single,_Allocator>::allocator;
			template<typename Info,typename _Allocator>
			class SegmentTree<Info,Single,Interval,_Allocator>{
			private:
				static _Allocator allocator;
				int n;
				Info*tr;
				void build(int p,int l,int r){
					if(l==r) return tr[p].init(l);
					int mid=(l+r)>>1;
					build(p<<1,l,mid),build(p<<1|1,mid+1,r);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				void modify(int p,int l,int r,int X,const Info&V){
					if(l==r) return tr[p].get(V);
					int mid=(l+r)>>1;
					X<=mid?modify(p<<1,l,mid,X,V):modify(p<<1|1,mid+1,r,X,V);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				Info query(int p,int l,int r,int L,int R){
					if(L<=l&&r<=R) return tr[p];
					int mid=(l+r)>>1;
					if(L<=mid&&R>mid) return merge(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
					else return L<=mid?query(p<<1,l,mid,L,R):query(p<<1|1,mid+1,r,L,R);
				}
			public:
				SegmentTree():n{}{tr=allocator.allocate(0);}
				void resize(int _n){allocator.deallocate(tr,n),tr=allocator.allocate((n=_n)<<2);}
				~SegmentTree(){allocator.deallocate(tr,n);}
				void build(){build(1,1,n);}
				void build(int _n){resize(_n),build(1,1,n);}
				void modify(int X,const Info&V){modify(1,1,n,X,V);}
				Info query(int L,int R){return query(1,1,n,L,R);}
			};
			template<typename Info,typename _Allocator>
			_Allocator SegmentTree<Info,Single,Interval,_Allocator>::allocator;
		}
	}
	// namespace Poly{
	// 	template<typename _Tp,typename _Transform>
	// 	class Poly{
	// 		static _Transform Trans;
	// 		_Tp*p;
	// 		uint n;
	// 	public:
	// 		constexpr const uint&length()const{return n;}
	// 		constexpr Poly():p{},n{}{}
	// 		constexpr Poly(const uint&_n):p{new _Tp[_n]{}},n{_n}{}
	// 		constexpr Poly(const std::initializer_list<_Tp>&L){
	// 			delete[] p,p=new _Tp[L.size()]{},n=0;
	// 			for(const _Tp&it:L) p[n++]=it;
	// 		}
	// 		constexpr void resize(const uint&_n){delete[] p,p=new _Tp[n=_n]{};}
	// 		constexpr Poly(const Poly&it){
	// 			delete[] p,p=new _Tp[n=it.n]{};
	// 			__builtin_memcpy(p,it.p,sizeof(_Tp)*it.n);
	// 		}
	// 		constexpr Poly&operator=(const Poly&it){
	// 			if(this==&it) return *this;
	// 			delete[] p,p=new _Tp[n=it.n]{};
	// 			memcpy(p,it.p,sizeof(_Tp)*it.n);
	// 			return *this;
	// 		}
	// 		constexpr Poly operator*(const Poly&it){
	// 			Poly ret{n+it.n};
	// 			Trans.init(n+it.n);
	// 			return ret;
	// 		}
	// 		constexpr _Tp&operator[](const uint&x){return p[x];}
	// 		constexpr const _Tp&operator[](const uint&x)const{return p[x];}
	// 		~Poly(){delete[] p;}
	// 	};
	// 	template<typename _Tp,typename _Transform>
	// 	_Transform Poly<_Tp,_Transform>::Trans;
	// }
}
using namespace Default_Source;

/**
 * 建立 9 个变量,来表示每种平局的出现次数。
 * RRR PPP SSS
 * RPS PSR SRP
 * RSP PRS SPR
 * 可以列方程组:
 * x1+x4+x7=AR
 * x2+x5+x8=AP
 * x3+x6+x9=AS
 * x1+x6+x8=BR
 * x2+x4+x9=BP
 * x3+x5+x7=BS
 * x1+x5+x9=CR
 * x2+x6+x7=CP
 * x3+x4+x8=CS
 * 然后考虑乱消一波元,然后会发现一些美好的性质。
 * 当然我们为了方便可以先浅记一些量:
 * y1=x2-x1,y2=x3-x2
 * y3=x5-x4,y4=x6-x5
 * y5=x8-x7,y6=x9-x8
 * 然后等我搞亿哈哈:
 * BR-AR=y3+y4+y5
 * BP-AP=-y3+y6
 * BS-AS=-y4-y5-y6
 * CR-BR=-y4+y6
 * CP-BP=y3+y4-y5-y6
 * CS-BS=-y3+y5
 * CR-AR=y3+y5+y6
 * CP-AP=y4-y5
 * CS-AS=-y3-y4-y6
 * y6-y5=CP-AP-CR+BR
 * ......
 * 消不出来,我是垃圾。
 * 去问了下山哥,发现不要手动乱试,这个更适合用瞪眼法。
 * 比如 y1=x2-x1,会和 AR,AP,BR,Bp,CR,CP 的方程有关。
 * 然后把这俩坨放在一起,发现除了 x1,x2,剩下的未知数都相同,就能消掉。
 * 所以:
 * y1=(AP+BP+CP-AR-BR-CR)/3
 * y2=(AS+BS+CS-AP-BP-CP)/3
 * y3=(AP+BS+CR-AR-BP-CS)/3
 * y4=(AS+BR+CP-AP-BS-CR)/3
 * y5=(AP+BR+CS-AR-BS-CP)/3
 * y6=(AS+BP+CR-AP-BR-CS)/3
 * 啊非常滴不错
 * 然后我们考虑计数的部分。
 * 大概就是枚举 x1+x2+x3=n 的情况,然后贡献是一个多重排列。
 * 非常滴不错。
 * 然后大概就是拆拆贡献分到 x1,x2,x3 三个东西上面,接着大力 NTT 卷上。
 * y1=x2-x1,y2=x3-x2
 * y3=x5-x4,y4=x6-x5
 * y5=x8-x7,y6=x9-x8
 * =>
 * x2=x1+y1,x3=x1+y1+y2
 * x5=x4+y3,x6=x4+y3+y4
 * x8=x7+y5,x9=x7+y5+y6
*/

template<typename _Tp>
const _Tp&max(const _Tp&lhs,const _Tp&rhs){return lhs<rhs?rhs:lhs;}
template<typename _Tp>
_Tp max(const std::initializer_list<_Tp>&L){
	_Tp ret=*L.begin();
	for(const _Tp&it:L) ret<it&&(ret=it);
	return ret;
}
template<typename _Tp>
void swap(_Tp&x,_Tp&y){
	static _Tp tmp;
	tmp=x,x=y,y=tmp;
}

using ull=unsigned long long;
constexpr uint N=1.5e6;
constexpr uint MAXLEN=1<<23;
constexpr ull mod=998244353,g=3;
constexpr ull qpow(ull x,int pw){
	ull ret=1;
	for(;pw;pw>>=1,x=x*x%mod) if(pw&1) ret=ret*x%mod;
	return ret;
}

IO::Fast_InStream<> Input;
IO::Fast_OutStream<> Output;

int n,Ar,Ap,As,Br,Bp,Bs,Cr,Cp,Cs;
ull fac[N+1],inv[N+1];

uint rev[MAXLEN],len;
ull Dragon[23],Fairy[23];
ull f1[MAXLEN],f4[MAXLEN];
void initRev(){for(uint i=0;i<len;++i) rev[i]=(rev[i>>1]>>1)|(i&1?len>>1:0);}
template<ull*p>
void Reverse(){for(uint i=0;i<len;++i) if(i<rev[i]) swap(p[i],p[rev[i]]);}
template<ull*omega,ull*p>
void NTT(){
	Reverse<p>();
	for(uint l=2,h=1,d=1;l<=len;h=l,l<<=1,++d){
		const ull step=omega[d];
		for(uint i=0;i<len;i+=l){
			ull*f=p+i,*g=f+h,tmp,omg{1};
			for(uint k=0;k<h;++k,omg=omg*step%mod)
				tmp=g[k]*omg%mod,g[k]=(f[k]+mod-tmp)%mod,f[k]=(f[k]+tmp)%mod;
		}
	}
}

signed main(){

	Input.read(n,Ar,Ap,As,Br,Bp,Bs,Cr,Cp,Cs);
	int y1=Ap+Bp+Cp-Ar-Br-Cr,y2=As+Bs+Cs-Ap-Bp-Cp,y3=Ap+Bs+Cr-Ar-Bp-Cs,y4=As+Br+Cp-Ap-Bs-Cr,y5=Ap+Br+Cs-Ar-Bs-Cp,y6=As+Bp+Cr-Ap-Br-Cs;
	if(y1%3||y2%3||y3%3||y4%3||y5%3||y6%3) return Output.write('0'),0;
	y1/=3,y2/=3,y3/=3,y4/=3,y5/=3,y6/=3;

	fac[0]=inv[0]=1;
	for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	inv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i;--i) inv[i]=inv[i+1]*(i+1ll)%mod;

	len=1u<<(33-__builtin_clz(Ar));
	for(uint k=0;k<23;++k) Dragon[k]=qpow(g,(mod-1)>>k);
	for(uint k=0;k<23;++k) Fairy[k]=qpow(Dragon[k],mod-2);
	initRev();
	for(int x1=max({0,-y1,-y1-y2});x1<=Ar;++x1) f1[x1]=fac[n]*inv[x1]%mod*inv[x1+y1]%mod*inv[x1+y1+y2]%mod;
	for(int x4=max({0,-y3,-y3-y4});x4<=Ar;++x4) f4[x4]=inv[x4]*inv[x4+y3]%mod*inv[x4+y3+y4]%mod;
	NTT<Dragon,f1>(),NTT<Dragon,f4>();
	for(uint i=0;i<len;++i) f1[i]=f1[i]*f4[i]%mod;
	NTT<Fairy,f1>();

	const ull _=qpow(len,mod-2);
	for(uint i=0;i<=Ar;++i) f1[i]=f1[i]*_%mod;
	ull ans=0;
	for(int x7=max({0,-y5,-y5-y6});x7<=Ar;++x7) ans=(ans+f1[Ar-x7]*inv[x7]%mod*inv[x7+y5]%mod*inv[x7+y5+y6])%mod;
	Output.write(ans);

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9416kb

input:

2
2 0 0
1 1 0
1 0 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1220kb

input:

3
0 1 2
3 0 0
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 46ms
memory: 17964kb

input:

333333
111111 111111 111111
111111 111111 111111
111111 111111 111111

output:

383902959

result:

ok 1 number(s): "383902959"

Test #4:

score: 0
Accepted
time: 196ms
memory: 51184kb

input:

1500000
500000 500000 500000
500000 500000 500000
500000 500000 500000

output:

355543262

result:

ok 1 number(s): "355543262"

Test #5:

score: 0
Accepted
time: 205ms
memory: 50460kb

input:

1499999
499999 499999 500001
499999 499999 500001
499999 499999 500001

output:

934301164

result:

ok 1 number(s): "934301164"

Test #6:

score: 0
Accepted
time: 28ms
memory: 30848kb

input:

1500000
1 0 1499999
1499999 1 0
0 1499999 1

output:

1500000

result:

ok 1 number(s): "1500000"

Test #7:

score: 0
Accepted
time: 28ms
memory: 29604kb

input:

1499999
0 749999 750000
750000 0 749999
749999 750000 0

output:

713966599

result:

ok 1 number(s): "713966599"

Test #8:

score: 0
Accepted
time: 1ms
memory: 9492kb

input:

1
1 0 0
0 0 1
0 1 0

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 1ms
memory: 9436kb

input:

1
0 1 0
0 1 0
0 1 0

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1224kb

input:

1
0 0 1
1 0 0
1 0 0

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 210ms
memory: 49124kb

input:

1499999
500000 500000 499999
499999 499999 500001
499999 499999 500001

output:

617065435

result:

ok 1 number(s): "617065435"

Test #12:

score: 0
Accepted
time: 0ms
memory: 9524kb

input:

2
1 1 0
0 0 2
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #13:

score: 0
Accepted
time: 210ms
memory: 50156kb

input:

1500000
500000 500001 499999
499999 500000 500001
499999 500000 500001

output:

925862004

result:

ok 1 number(s): "925862004"

Test #14:

score: 0
Accepted
time: 96ms
memory: 29328kb

input:

629197
210878 201408 216911
145293 266423 217481
194751 220179 214267

output:

447295633

result:

ok 1 number(s): "447295633"

Test #15:

score: 0
Accepted
time: 99ms
memory: 26816kb

input:

579097
200209 204257 174631
149110 148890 281097
138034 263752 177311

output:

71830925

result:

ok 1 number(s): "71830925"

Test #16:

score: 0
Accepted
time: 44ms
memory: 18140kb

input:

354224
100316 63899 190009
69306 123829 161089
140523 76088 137613

output:

44852283

result:

ok 1 number(s): "44852283"

Test #17:

score: 0
Accepted
time: 190ms
memory: 48332kb

input:

1229851
383009 323934 522908
551226 311238 367387
547622 353128 329101

output:

39721313

result:

ok 1 number(s): "39721313"

Test #18:

score: 0
Accepted
time: 104ms
memory: 31048kb

input:

858452
195309 312080 351063
384805 51797 421850
200466 301164 356822

output:

506491992

result:

ok 1 number(s): "506491992"

Test #19:

score: 0
Accepted
time: 382ms
memory: 69156kb

input:

1424218
661653 323895 438670
467846 488045 468327
369769 343207 711242

output:

782021141

result:

ok 1 number(s): "782021141"

Test #20:

score: 0
Accepted
time: 186ms
memory: 44576kb

input:

1079733
333391 427895 318447
579853 153924 345956
406031 300755 372947

output:

111229812

result:

ok 1 number(s): "111229812"

Test #21:

score: 0
Accepted
time: 90ms
memory: 28496kb

input:

572270
168517 197624 206129
238722 154914 178634
192692 145891 233687

output:

93444378

result:

ok 1 number(s): "93444378"

Test #22:

score: 0
Accepted
time: 50ms
memory: 23872kb

input:

470911
95201 196020 179690
143795 173744 153372
142604 154489 173818

output:

629148200

result:

ok 1 number(s): "629148200"

Test #23:

score: 0
Accepted
time: 88ms
memory: 24352kb

input:

514907
142312 117185 255410
52426 249434 213047
180346 59381 275180

output:

497502651

result:

ok 1 number(s): "497502651"

Test #24:

score: 0
Accepted
time: 93ms
memory: 27640kb

input:

406588
151239 177967 77382
93189 144948 168451
94378 135309 176901

output:

790871601

result:

ok 1 number(s): "790871601"

Test #25:

score: 0
Accepted
time: 23ms
memory: 12764kb

input:

175290
55982 60345 58963
48359 77923 49008
23679 74616 76995

output:

123245869

result:

ok 1 number(s): "123245869"

Test #26:

score: 0
Accepted
time: 211ms
memory: 47320kb

input:

1387914
512757 474809 400348
378268 216654 792992
649332 374567 364015

output:

676034326

result:

ok 1 number(s): "676034326"

Test #27:

score: 0
Accepted
time: 92ms
memory: 31880kb

input:

764222
219470 230830 313922
331893 97293 335036
97220 292440 374562

output:

158682546

result:

ok 1 number(s): "158682546"

Test #28:

score: 0
Accepted
time: 98ms
memory: 31784kb

input:

753135
242199 294626 216310
175239 287120 290776
282985 150249 319901

output:

971077263

result:

ok 1 number(s): "971077263"

Test #29:

score: 0
Accepted
time: 101ms
memory: 33272kb

input:

907648
254368 314623 338657
266634 210330 430684
203259 377229 327160

output:

657924076

result:

ok 1 number(s): "657924076"

Test #30:

score: 0
Accepted
time: 180ms
memory: 40728kb

input:

734407
287960 273092 173355
91803 383817 258787
317856 268839 147712

output:

302163640

result:

ok 1 number(s): "302163640"

Test #31:

score: 0
Accepted
time: 188ms
memory: 42096kb

input:

802408
296016 284435 221957
207041 242882 352485
117792 274366 410250

output:

54247530

result:

ok 1 number(s): "54247530"

Test #32:

score: 0
Accepted
time: 85ms
memory: 29672kb

input:

562487
158889 225035 178563
148413 302399 111675
148133 215119 199235

output:

169658542

result:

ok 1 number(s): "169658542"

Test #33:

score: 0
Accepted
time: 183ms
memory: 45988kb

input:

999120
389537 311486 298097
316708 332443 349969
261915 402318 334887

output:

352258886

result:

ok 1 number(s): "352258886"

Test #34:

score: 0
Accepted
time: 186ms
memory: 47396kb

input:

1409159
427245 484076 497838
435890 528804 444465
588832 314386 505941

output:

887383005

result:

ok 1 number(s): "887383005"

Test #35:

score: 0
Accepted
time: 186ms
memory: 45908kb

input:

1003619
340241 274051 389327
166457 383901 453261
211841 434615 357163

output:

353962733

result:

ok 1 number(s): "353962733"

Test #36:

score: 0
Accepted
time: 5ms
memory: 9756kb

input:

22574
9246 5094 8234
9209 7482 5883
12089 6331 4154

output:

60839910

result:

ok 1 number(s): "60839910"

Test #37:

score: 0
Accepted
time: 191ms
memory: 47208kb

input:

1415532
478588 564750 372194
512789 526677 376066
217017 566262 632253

output:

625939628

result:

ok 1 number(s): "625939628"

Test #38:

score: 0
Accepted
time: 90ms
memory: 28188kb

input:

662723
241713 270544 150466
205318 236372 221033
329239 165257 168227

output:

186211005

result:

ok 1 number(s): "186211005"

Test #39:

score: 0
Accepted
time: 357ms
memory: 64708kb

input:

1096822
586933 218335 291554
392825 346250 357747
326051 392267 378504

output:

128569855

result:

ok 1 number(s): "128569855"

Test #40:

score: 0
Accepted
time: 189ms
memory: 46696kb

input:

1246485
277064 449274 520147
467862 333900 444723
590215 427647 228623

output:

695555486

result:

ok 1 number(s): "695555486"

Test #41:

score: 0
Accepted
time: 47ms
memory: 20080kb

input:

351715
120661 101781 129273
142995 80157 128563
169330 148880 33505

output:

466480620

result:

ok 1 number(s): "466480620"

Test #42:

score: 0
Accepted
time: 199ms
memory: 43312kb

input:

905498
381722 200474 323302
202271 344030 359197
350698 364396 190404

output:

346377686

result:

ok 1 number(s): "346377686"

Test #43:

score: 0
Accepted
time: 106ms
memory: 34524kb

input:

1064626
261709 325862 477055
516569 367130 180927
307746 452237 304643

output:

557495758

result:

ok 1 number(s): "557495758"

Test #44:

score: 0
Accepted
time: 0ms
memory: 1332kb

input:

494104
224009 132488 137607
15527 180865 297712
203418 197294 93392

output:

0

result:

ok 1 number(s): "0"

Test #45:

score: 0
Accepted
time: 0ms
memory: 1216kb

input:

1153008
315731 708637 128640
128519 347757 676732
267014 535519 350475

output:

0

result:

ok 1 number(s): "0"

Test #46:

score: 0
Accepted
time: 368ms
memory: 68276kb

input:

1470490
550743 481409 438338
763576 96662 610252
363836 262517 844137

output:

964914867

result:

ok 1 number(s): "964914867"

Test #47:

score: 0
Accepted
time: 47ms
memory: 17612kb

input:

476270
72377 235854 168039
1528 311122 163620
254184 15707 206379

output:

0

result:

ok 1 number(s): "0"

Test #48:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

787189
201940 129464 455785
243491 290356 253342
257543 326980 202666

output:

0

result:

ok 1 number(s): "0"

Test #49:

score: 0
Accepted
time: 0ms
memory: 1224kb

input:

1311581
662049 427399 222133
182392 768551 360638
257311 534768 519502

output:

0

result:

ok 1 number(s): "0"

Test #50:

score: 0
Accepted
time: 41ms
memory: 18820kb

input:

215077
105142 95920 14015
37417 106030 71630
97785 86292 31000

output:

0

result:

ok 1 number(s): "0"

Test #51:

score: 0
Accepted
time: 0ms
memory: 1332kb

input:

680614
190222 59142 431250
229277 326583 124754
244226 267501 168887

output:

0

result:

ok 1 number(s): "0"

Test #52:

score: 0
Accepted
time: 0ms
memory: 1296kb

input:

599441
163256 359629 76556
269072 153998 176371
296850 273987 28604

output:

0

result:

ok 1 number(s): "0"

Test #53:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

1186565
664884 314828 206853
50093 597130 539342
352770 117639 716156

output:

0

result:

ok 1 number(s): "0"

Test #54:

score: 0
Accepted
time: 0ms
memory: 1296kb

input:

399589
160429 157151 82009
52807 151045 195737
168413 46646 184530

output:

0

result:

ok 1 number(s): "0"

Test #55:

score: 0
Accepted
time: 174ms
memory: 36156kb

input:

498263
277597 129082 91584
146928 169294 182041
198001 220974 79288

output:

20392590

result:

ok 1 number(s): "20392590"

Test #56:

score: 0
Accepted
time: 373ms
memory: 68828kb

input:

1287548
598441 439788 249319
532780 427274 327494
984985 96121 206442

output:

157485795

result:

ok 1 number(s): "157485795"

Test #57:

score: 0
Accepted
time: 0ms
memory: 1276kb

input:

1435275
447804 724373 263098
383152 619901 432222
383304 68399 983572

output:

0

result:

ok 1 number(s): "0"

Test #58:

score: 0
Accepted
time: 0ms
memory: 1216kb

input:

699090
240262 213752 245076
255039 260728 183323
234619 115480 348991

output:

0

result:

ok 1 number(s): "0"

Test #59:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

972438
478545 285919 207974
128489 319801 524148
286253 298521 387664

output:

0

result:

ok 1 number(s): "0"

Test #60:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

331352
121624 30247 179481
80755 93304 157293
62835 160621 107896

output:

0

result:

ok 1 number(s): "0"

Test #61:

score: 0
Accepted
time: 0ms
memory: 1224kb

input:

425318
161870 195187 68261
58421 111518 255379
98211 149256 177851

output:

0

result:

ok 1 number(s): "0"

Test #62:

score: 0
Accepted
time: 0ms
memory: 1232kb

input:

592741
319914 259579 13248
148647 194672 249422
378967 175386 38388

output:

0

result:

ok 1 number(s): "0"

Test #63:

score: 0
Accepted
time: 25ms
memory: 17668kb

input:

602228
34962 454429 112837
247881 315495 38852
384357 69191 148680

output:

0

result:

ok 1 number(s): "0"

Test #64:

score: 0
Accepted
time: 0ms
memory: 1336kb

input:

610389
373522 193737 43130
62839 130072 417478
138346 203349 268694

output:

0

result:

ok 1 number(s): "0"

Test #65:

score: 0
Accepted
time: 42ms
memory: 13676kb

input:

161360
82645 44242 34473
66788 59603 34969
48139 22450 90771

output:

559061811

result:

ok 1 number(s): "559061811"

Test #66:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

591506
92336 192103 307067
13873 290990 286643
28921 254667 307918

output:

0

result:

ok 1 number(s): "0"

Test #67:

score: 0
Accepted
time: 199ms
memory: 42236kb

input:

940718
486143 39848 414727
438813 358245 143660
200948 304832 434938

output:

189368763

result:

ok 1 number(s): "189368763"

Test #68:

score: 0
Accepted
time: 0ms
memory: 1212kb

input:

585970
36092 336501 213377
217719 134212 234039
454324 31689 99957

output:

0

result:

ok 1 number(s): "0"

Test #69:

score: 0
Accepted
time: 0ms
memory: 1228kb

input:

814985
350619 424060 40306
318150 477415 19420
296376 381374 137235

output:

0

result:

ok 1 number(s): "0"

Test #70:

score: 0
Accepted
time: 363ms
memory: 67096kb

input:

1212624
635151 355933 221540
382996 340761 488867
28683 189420 994521

output:

0

result:

ok 1 number(s): "0"

Test #71:

score: 0
Accepted
time: 0ms
memory: 1332kb

input:

825460
28354 541876 255230
334422 299199 191839
166016 391674 267770

output:

0

result:

ok 1 number(s): "0"

Test #72:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

644697
305286 296842 42569
165080 234255 245362
127688 459557 57452

output:

0

result:

ok 1 number(s): "0"

Test #73:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

604964
3223 299494 302247
292154 126107 186703
77013 270881 257070

output:

0

result:

ok 1 number(s): "0"

Test #74:

score: 0
Accepted
time: 0ms
memory: 1248kb

input:

3
0 1 2
1 1 1
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #75:

score: 0
Accepted
time: 1ms
memory: 9508kb

input:

4
2 0 2
2 1 1
2 2 0

output:

24

result:

ok 1 number(s): "24"

Test #76:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

2
1 1 0
1 0 1
0 2 0

output:

0

result:

ok 1 number(s): "0"

Test #77:

score: 0
Accepted
time: 0ms
memory: 1336kb

input:

3
2 1 0
0 1 2
1 2 0

output:

0

result:

ok 1 number(s): "0"

Test #78:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

3
0 1 2
1 0 2
0 1 2

output:

0

result:

ok 1 number(s): "0"

Test #79:

score: 0
Accepted
time: 0ms
memory: 1336kb

input:

2
0 2 0
1 0 1
0 1 1

output:

0

result:

ok 1 number(s): "0"

Test #80:

score: 0
Accepted
time: 0ms
memory: 1332kb

input:

4
1 2 1
0 2 2
0 2 2

output:

0

result:

ok 1 number(s): "0"

Test #81:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

1
0 0 1
0 0 1
0 1 0

output:

0

result:

ok 1 number(s): "0"

Test #82:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

3
1 0 2
1 2 0
2 1 0

output:

0

result:

ok 1 number(s): "0"

Test #83:

score: 0
Accepted
time: 0ms
memory: 9508kb

input:

3
0 1 2
2 0 1
0 1 2

output:

6

result:

ok 1 number(s): "6"

Test #84:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

3
1 1 1
2 0 1
0 1 2

output:

0

result:

ok 1 number(s): "0"

Test #85:

score: 0
Accepted
time: 0ms
memory: 1272kb

input:

4
1 1 2
1 1 2
2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #86:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

2
0 2 0
1 0 1
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #87:

score: 0
Accepted
time: 0ms
memory: 1216kb

input:

2
0 0 2
1 0 1
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #88:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

2
0 1 1
0 2 0
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #89:

score: 0
Accepted
time: 0ms
memory: 1324kb

input:

3
2 0 1
1 1 1
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #90:

score: 0
Accepted
time: 1ms
memory: 9492kb

input:

5
1 2 2
1 2 2
1 2 2

output:

270

result:

ok 1 number(s): "270"

Test #91:

score: 0
Accepted
time: 0ms
memory: 1224kb

input:

3
2 1 0
1 0 2
0 1 2

output:

0

result:

ok 1 number(s): "0"

Test #92:

score: 0
Accepted
time: 0ms
memory: 1276kb

input:

3
2 1 0
1 0 2
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #93:

score: 0
Accepted
time: 0ms
memory: 1224kb

input:

4
2 1 1
1 2 1
0 2 2

output:

0

result:

ok 1 number(s): "0"

Test #94:

score: 0
Accepted
time: 0ms
memory: 1296kb

input:

2
0 1 1
2 0 0
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #95:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

2
2 0 0
1 1 0
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #96:

score: 0
Accepted
time: 0ms
memory: 1300kb

input:

4
2 1 1
1 2 1
1 2 1

output:

0

result:

ok 1 number(s): "0"

Test #97:

score: 0
Accepted
time: 0ms
memory: 9416kb

input:

3
2 1 0
1 1 1
1 2 0

output:

6

result:

ok 1 number(s): "6"

Test #98:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

2
0 2 0
1 0 1
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #99:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

2
0 0 2
2 0 0
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #100:

score: 0
Accepted
time: 0ms
memory: 9404kb

input:

2
1 0 1
0 0 2
0 1 1

output:

2

result:

ok 1 number(s): "2"

Test #101:

score: 0
Accepted
time: 0ms
memory: 1280kb

input:

2
0 0 2
2 0 0
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #102:

score: 0
Accepted
time: 0ms
memory: 1328kb

input:

3
1 0 2
0 1 2
2 1 0

output:

0

result:

ok 1 number(s): "0"