QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18062#992. Number of Colorful MatchingsAppleblue17#AC ✓266ms17060kbC++3.9kb2022-01-16 07:19:312022-05-04 17:00:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 17:00:42]
  • 评测
  • 测评结果:AC
  • 用时:266ms
  • 内存:17060kb
  • [2022-01-16 07:19:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long N=660,mod=2;
long long n;
long long a[N][N],b[N][N],p[N][N];
long long f[N][N],ex;

long long ksm(long long a,long long x){
	long long tot=1;
	while(x){
		if(x&1) tot=tot*a%mod;
		a=a*a%mod;
		x>>=1ll;
	}
	return tot;
}

long long det(long long a[N][N],long long n){
	long long tot=1;
	for(long long k=1;k<=n;k++){
		long long st=0;
		for(long long i=k;i<=n;i++){
			if(a[i][k]){
				st=i;
				break;
			}
		}
		if(!st) return 0;
		
		if(st!=k){
			for(long long j=1;j<=n;j++) swap(a[k][j],a[st][j]);
			tot=mod-tot;
		}
		for(long long i=k+1;i<=n;i++){
			long long x=a[i][k]*ksm(a[k][k],mod-2)%mod;
			for(long long j=1;j<=n;j++) a[i][j]=(a[i][j]+mod-x*a[k][j]%mod)%mod;
		}
		tot=tot*a[k][k]%mod;
	}
	return tot;
}

void gauss(long long a[N][N],long long n){
	for(long long k=1;k<n;k++){
		long long st=0;
		for(long long i=k+1;i<=n;i++){
			if(a[i][k]){
				st=i;
				break;
			}
		}
		if(!st) continue;
		
		
		if(st!=k+1){
			for(long long j=1;j<=n;j++) swap(a[k+1][j],a[st][j]);
			for(long long j=1;j<=n;j++) swap(a[j][k+1],a[j][st]);
		}
		for(long long i=k+2;i<=n;i++){
			long long x=a[i][k]*ksm(a[k+1][k],mod-2)%mod;
			for(long long j=1;j<=n;j++)
				a[i][j]=(a[i][j]+mod-a[k+1][j]*x%mod)%mod;
			for(long long j=1;j<=n;j++)
				a[j][k+1]=(a[j][k+1]+a[j][i]*x%mod)%mod;
		}
	}
	f[0][0]=1;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<i;j++){
			long long tot=a[j][i];
			for(long long k=j;k<i;k++) tot=tot*(mod-a[k+1][k])%mod;
			for(long long t=0;t<=i;t++) f[i][t]=(f[i][t]+f[j-1][t]*tot%mod)%mod;
		}
		for(long long t=0;t<=i;t++) f[i][t]=(f[i][t]+f[i-1][t]*a[i][i]%mod)%mod;
		for(long long t=1;t<=i;t++) f[i][t]=(f[i][t]+f[i-1][t-1])%mod;
	}
}

bool INV(long long a[N][N],long long b[N][N],long long n){
	for(long long k=1;k<=n;k++){
		long long st=0;
		
		while(1){
			for(long long i=k;i<=n;i++){
				if(b[i][k]){
					st=i;
					break;
				}
			}
			if(st) break;
			
			long long q=0;
			for(long long j=k;j<=n;j++){
				if(b[k][j]){
					q=j;
					break;
				}
			}
			if(q){
				for(long long i=1;i<=n;i++) swap(b[i][k],b[i][q]),swap(a[i][k],a[i][q]),swap(p[i][k],p[i][q]);
			}
			else{
				ex++;
				if(ex>n) return 0;
				for(long long j=1;j<=n;j++) b[k][j]=a[k][j],a[k][j]=0;
				for(long long i=1;i<k;i++){
					long long x=b[k][i]*ksm(b[i][i],mod-2)%mod;
					for(long long j=1;j<=n;j++)
						b[k][j]=(b[k][j]+mod-b[i][j]*x%mod)%mod,
						a[k][j]=(a[k][j]+mod-a[i][j]*x%mod)%mod,
						p[k][j]=(p[k][j]+mod-p[i][j]*x%mod)%mod;
				}
			}
		}
		
		if(st!=k){
			for(long long j=1;j<=n;j++) swap(b[k][j],b[st][j]),swap(a[k][j],a[st][j]),swap(p[k][j],p[st][j]);
		}
		for(long long i=1;i<=n;i++){
			if(i==k) continue;
			long long x=b[i][k]*ksm(b[k][k],mod-2)%mod;
			for(long long j=1;j<=n;j++)
				b[i][j]=(b[i][j]+mod-b[k][j]*x%mod)%mod,
				a[i][j]=(a[i][j]+mod-a[k][j]*x%mod)%mod,
				p[i][j]=(p[i][j]+mod-p[k][j]*x%mod)%mod;
		}
	}
	for(long long k=n;k>=1;k--){
		long long x=ksm(b[k][k],mod-2);
		for(long long j=1;j<=n;j++)
			b[k][j]=b[k][j]*x%mod,a[k][j]=a[k][j]*x%mod,p[k][j]=p[k][j]*x%mod;
		
		for(long long i=k+1;i<=n;i++){
			long long x=b[k][i];
			for(long long j=1;j<=n;j++){
				b[k][j]=(b[k][j]+mod-b[i][j]*x%mod)%mod,
				a[k][j]=(a[k][j]+mod-a[i][j]*x%mod)%mod,
				p[k][j]=(p[k][j]+mod-p[i][j]*x%mod)%mod;
			}
		}
	}
	return 1;
}


int main(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		char s[N];
		scanf("\n%s",s+1);
		for(long long j=1;j<=n;j++) b[i][j]=s[j]-'0';
	}
	for(long long i=1;i<=n;i++){
		char s[N];
		scanf("\n%s",s+1);
		for(long long j=1;j<=n;j++) a[i][j]=s[j]-'0';
	}
	for(long long i=1;i<=n;i++) p[i][i]=1;
	if(!INV(a,b,n)){
		for(long long i=0;i<=n;i++) cout<<0<<" ";
		return 0;
	}
	gauss(a,n);
	
	long long x=ksm(det(p,n),mod-2);
	for(long long i=ex;i<=n;i++) cout<<f[n][i]*x%mod<<endl;
	for(long long i=1;i<=ex;i++) cout<<0<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 9800kb

input:

2
11
10
00
11

output:

0
0
1

result:

ok 3 tokens

Test #2:

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

input:

10
0100110000
0000010111
0111000111
1000101100
1101000001
1111110000
1001001110
0000000011
0001000010
0100100110
1100010101
0001000001
0001001010
0011100111
0010101111
1001011011
1001100111
0111101001
0010100010
0001111011

output:

0
0
0
1
1
1
1
1
0
0
1

result:

ok 11 tokens

Test #3:

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

input:

18
001100000000010111
011100011110001011
001101000001111111
000010010011100000
000011000100001001
001001101100010101
000100000100010010
100011100111001010
111110010110111001
100111011110100100
101000100001111011
110000100101011111
101011001000000111
110001011110010101
110010011111001110
001001011100...

output:

0
0
0
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0

result:

ok 19 tokens

Test #4:

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

input:

18
110000000001011101
110001111000101100
110100000111111100
001001001110000000
001100010000100100
100110110001010100
010000010001001010
001110011100101011
111001011011100110
011101111010010010
100010000111101111
000010010101111110
101100100000011111
000101111001010111
001001111100111000
100101110010...

output:

0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
0
1
1
0

result:

ok 19 tokens

Test #5:

score: 0
Accepted
time: 266ms
memory: 15360kb

input:

300
00000000010111011100011110001011001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000...

output:

0
0
0
0
0
1
1
1
0
1
1
1
0
0
0
1
1
0
1
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
1
0
0
1
0
0
1
1
1
1
0
0
0
1
1
0
1
1
1
0
0
1
1
1
1
0
1
1
0
0
1
0
1
1
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
0
1
1
0
0
1
0
1
1
...

result:

ok 301 tokens

Test #6:

score: 0
Accepted
time: 262ms
memory: 16728kb

input:

300
00000001011101110001111000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001...

output:

0
0
0
1
0
1
1
0
0
0
0
1
1
1
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
0
1
1
1
1
1
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
0
1
1
0
0
0
1
1
1
0
1
1
0
1
0
1
0
0
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
1
0
1
1
0
1
0
1
...

result:

ok 301 tokens

Test #7:

score: 0
Accepted
time: 254ms
memory: 16804kb

input:

300
00000101110111000111100010110011010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111001000100100000000000111...

output:

0
0
0
0
0
1
1
1
1
0
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
1
0
1
1
1
1
1
1
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
0
1
1
0
1
0
1
0
1
0
0
0
0
1
0
1
1
1
0
0
0
0
1
1
0
1
1
1
0
1
1
0
0
1
1
1
0
0
0
1
0
0
1
0
1
1
1
...

result:

ok 301 tokens

Test #8:

score: 0
Accepted
time: 84ms
memory: 12796kb

input:

200
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 tokens

Test #9:

score: 0
Accepted
time: 131ms
memory: 16652kb

input:

230
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
1
0
0
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 231 tokens

Test #10:

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

input:

270
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000...

output:

0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 271 tokens

Test #11:

score: 0
Accepted
time: 263ms
memory: 15452kb

input:

300
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 301 tokens

Test #12:

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

input:

50
11000111100010110011010000011111110000100100111000
00000011000100001001001001101100010101000100000100
01001010001110011100101011111001011011100110011101
11101001001010001000011110111100001001010111111010
11001000000111110001011110010101110010011111001110
001001011100100010010000000000011101110101...

output:

0
1
1
1
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
0
0
1
0
1
0
1
1
1
1
0
0
1
1

result:

ok 51 tokens

Test #13:

score: 0
Accepted
time: 12ms
memory: 12288kb

input:

80
00011110001011001101000001111111000010010011100000000011000100001001001001101100
01010100010000010001001010001110011100101011111001011011100110011101111010010010
10001000011110111100001001010111111010110010000001111100010111100101011100100111
110011100010010111001000100100000000000111011101011011...

output:

0
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
1
1
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
1
0
1
0
1
0
0
1
0
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
0
0
0
0
0
1
0
0
1
0
1
1
0
0

result:

ok 81 tokens

Test #14:

score: 0
Accepted
time: 15ms
memory: 12472kb

input:

120
011110001011001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010
111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111
001110001001011100100010010000000000011101110101101110...

output:

0
1
0
0
1
0
1
0
0
1
1
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
1
0
1
1
0
0
1
1
1
0
1
1
1
0
0
0
1
0
1
0
1
1
1
1
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0

result:

ok 121 tokens

Test #15:

score: 0
Accepted
time: 63ms
memory: 12772kb

input:

180
111000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010
0101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000011101110101101110100...

output:

0
1
0
0
1
1
1
1
0
1
1
0
1
0
0
0
1
1
0
0
0
0
0
1
1
1
0
0
1
1
0
0
0
1
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
0
0
1
0
0
1
0
1
0
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
0
0
1
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
1
1
0
1
1
1
1
0
0
1
0
1
1
1
0
1
1
0
1
1
1
1
1
0
0
0
1
1
...

result:

ok 181 tokens

Test #16:

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

input:

220
1000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001
010111001001111100111000100101110010001001000000000001110111010110111010011...

output:

1
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
1
1
0
1
1
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
1
1
1
1
0
0
1
1
0
0
0
0
0
1
1
1
0
0
0
1
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
0
...

result:

ok 221 tokens

Test #17:

score: 0
Accepted
time: 153ms
memory: 16908kb

input:

250
0010110011010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111
001000100100000000000111011101011011101001111...

output:

0
1
1
1
0
1
1
0
0
1
1
0
1
0
0
0
1
0
0
1
1
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
1
1
1
1
1
0
1
1
0
1
0
0
0
1
0
0
0
0
0
1
0
1
1
0
1
1
0
0
1
1
1
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
0
1
1
1
0
0
1
0
0
0
1
1
0
1
1
1
1
0
1
1
0
0
1
1
0
1
1
1
1
0
0
0
0
1
1
1
0
1
1
0
1
0
...

result:

ok 251 tokens

Test #18:

score: 0
Accepted
time: 202ms
memory: 15192kb

input:

270
101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001
1101110101101110100111111...

output:

0
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
1
1
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
0
0
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
0
1
0
1
0
0
1
1
1
1
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
0
1
1
0
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
0
1
1
0
0
0
0
1
0
0
...

result:

ok 271 tokens

Test #19:

score: 0
Accepted
time: 264ms
memory: 15440kb

input:

300
11001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000011101110101101110100111111110...

output:

0
0
0
0
1
0
1
0
0
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
0
0
0
1
1
1
0
0
1
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
1
0
0
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
...

result:

ok 301 tokens

Test #20:

score: 0
Accepted
time: 259ms
memory: 15496kb

input:

300
00110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001110111010110111010011111111010...

output:

1
1
0
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
1
1
0
0
0
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
1
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
...

result:

ok 301 tokens

Test #21:

score: 0
Accepted
time: 262ms
memory: 17060kb

input:

300
11010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111001000100100000000000111011101011011101001111111101001...

output:

0
1
0
1
0
1
1
0
1
1
0
0
0
0
1
1
1
0
1
1
0
0
1
1
0
0
0
1
0
0
0
1
1
0
1
1
1
0
1
1
1
1
1
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
0
0
1
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
1
1
0
0
1
0
1
0
0
0
1
1
0
1
0
1
0
0
1
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
1
1
0
0
1
0
0
1
0
1
0
0
1
0
0
...

result:

ok 301 tokens