QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96689#5107. Mosaic BrowsingmarcoskAC ✓195ms95060kbC++233.8kb2023-04-15 02:56:562023-04-15 02:56:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-15 02:56:59]
  • 评测
  • 测评结果:AC
  • 用时:195ms
  • 内存:95060kb
  • [2023-04-15 02:56:56]
  • 提交

answer

#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

// MAXN must be power of 2 !!
// MOD-1 needs to be a multiple of MAXN !!
// big mod and primitive root for NTT:
typedef ll tf;
typedef vector<tf> poly;
const tf MOD=2305843009255636993,RT=5,MAXN=1<<21;
// FFT
struct CD {
	double r,i;
	CD(double r=0, double i=0):r(r),i(i){}
	double real()const{return r;}
	void operator/=(const int c){r/=c, i/=c;}
};
CD operator*(const CD& a, const CD& b){
	return CD(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}
CD operator+(const CD& a, const CD& b){return CD(a.r+b.r,a.i+b.i);}
CD operator-(const CD& a, const CD& b){return CD(a.r-b.r,a.i-b.i);}
const double pi=acos(-1.0);
// NTT
/*
struct CD {
	tf x;
	CD(tf x):x(x){}
	CD(){}
};
CD operator*(const CD& a, const CD& b){return CD(mulmod(a.x,b.x));}
CD operator+(const CD& a, const CD& b){return CD(addmod(a.x,b.x));}
CD operator-(const CD& a, const CD& b){return CD(submod(a.x,b.x));}
vector<tf> rts(MAXN+9,-1);
CD root(int n, bool inv){
	tf r=rts[n]<0?rts[n]=pm(RT,(MOD-1)/n):rts[n];
	return CD(inv?pm(r,MOD-2):r);
}
*/
CD cp1[MAXN+9],cp2[MAXN+9];
int R[MAXN+9];
void dft(CD* a, int n, bool inv){
	fore(i,0,n)if(R[i]<i)swap(a[R[i]],a[i]);
	for(int m=2;m<=n;m*=2){
		double z=2*pi/m*(inv?-1:1); // FFT
		CD wi=CD(cos(z),sin(z)); // FFT
		// CD wi=root(m,inv); // NTT
		for(int j=0;j<n;j+=m){
			CD w(1);
			for(int k=j,k2=j+m/2;k2<j+m;k++,k2++){
				CD u=a[k];CD v=a[k2]*w;a[k]=u+v;a[k2]=u-v;w=w*wi;
			}
		}
	}
	if(inv)fore(i,0,n)a[i]/=n; // FFT
	//if(inv){ // NTT
	//	CD z(pm(n,MOD-2)); // pm: modular exponentiation
	//	fore(i,0,n)a[i]=a[i]*z;
	//}
}
poly multiply(poly& p1, poly& p2){
	int n=p1.size()+p2.size()+1;
	int m=1,cnt=0;
	while(m<=n)m+=m,cnt++;
	fore(i,0,m){R[i]=0;fore(j,0,cnt)R[i]=(R[i]<<1)|((i>>j)&1);}
	fore(i,0,m)cp1[i]=0,cp2[i]=0;
	fore(i,0,p1.size())cp1[i]=p1[i];
	fore(i,0,p2.size())cp2[i]=p2[i];
	dft(cp1,m,false);dft(cp2,m,false);
	fore(i,0,m)cp1[i]=cp1[i]*cp2[i];
	dft(cp1,m,true);
	poly res;
	n-=2;
	fore(i,0,n)res.pb((tf)floor(cp1[i].real()+0.5)); // FFT
	//fore(i,0,n)res.pb(cp1[i].x); // NTT
	return res;
}

poly add(poly p, poly q){
	int n=SZ(p),m=SZ(q);
	poly ans(max(n,m));
	fore(i,0,n) ans[i]+=p[i];
	fore(i,0,m) ans[i]+=q[i];
	return ans;
}

poly sub(poly p, poly q){
	int n=SZ(p),m=SZ(q);
	poly ans(max(n,m));
	fore(i,0,n) ans[i]+=p[i];
	fore(i,0,m) ans[i]-=q[i];
	return ans;
}

int main(){FIN;
	int n1,m1; cin>>n1>>m1;
	vector<vector<int>> a(n1,vector<int>(m1));
	fore(i,0,n1) fore(j,0,m1) cin>>a[i][j];
	
	int n2,m2; cin>>n2>>m2;
	vector<vector<int>> b(n2,vector<int>(m2));
	fore(i,0,n2) fore(j,0,m2) cin>>b[i][j];
	
	
	poly p;
	fore(i,0,n1){
		fore(j,0,m1) p.pb(a[i][j]);
		if(i!=n1-1) fore(j,0,m2-m1) p.pb(0);
	}
	
	poly q;
	fore(i,0,n2) fore(j,0,m2) q.pb(b[i][j]);
	
	// (p-q)^2 = p^2 - 2*p*q + q^2
	
	ll sum2=0;
	for(auto &x:p) sum2+=x*x;
	auto sq=q;
	for(auto &x:sq) x=x*x;
	fore(i,1,SZ(sq)) sq[i]+=sq[i-1];
	
	poly qr=p;
	reverse(ALL(qr));
	
	poly now=multiply(q,qr);
	poly me;
	fore(i,0,SZ(q)-SZ(p)+1){
	  ll val=sq[i+SZ(p)-1]; if(i) val-=sq[i-1];
	  val-=2ll*now[SZ(p)+i-1];
	  val+=sum2;
	  me.pb(val);
	}
	
	//(p0*q^2)
	poly p0=p;
	for(auto &x:p0) x=x==0;
	for(auto &x:q) x=x*x;
	reverse(ALL(p0));
	poly now2=multiply(p0,q);
	poly he;
	fore(i,0,SZ(q)-SZ(p0)+1) he.pb(now2[SZ(p)+i-1]);

	// (p-q)^2 - (p0*q^2)
	poly ans=sub(me,he);
	
	vector<ii> res;
	
	fore(i,0,n2) fore(j,0,m2) if(i+n1<=n2 && j+m1<=m2 && ans[m2*i+j]==0){
		res.pb({i,j});
	}
	
	cout<<SZ(res)<<"\n";
	for(auto x:res)cout<<x.fst+1<<" "<<x.snd+1<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 174ms
memory: 93860kb

input:

100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

2005
1 1
1 101
1 201
1 301
1 401
2 1
2 101
2 201
2 301
2 401
3 1
3 101
3 201
3 301
3 401
4 1
4 101
4 201
4 301
4 401
5 1
5 101
5 201
5 301
5 401
6 1
6 101
6 201
6 301
6 401
7 1
7 101
7 201
7 301
7 401
8 1
8 101
8 201
8 301
8 401
9 1
9 101
9 201
9 301
9 401
10 1
10 101
10 201
10 301
10 401
11 1
11 10...

result:

ok 2006 lines

Test #2:

score: 0
Accepted
time: 177ms
memory: 91652kb

input:

250 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

1255
1 1
1 101
1 201
1 301
1 401
2 1
2 101
2 201
2 301
2 401
3 1
3 101
3 201
3 301
3 401
4 1
4 101
4 201
4 301
4 401
5 1
5 101
5 201
5 301
5 401
6 1
6 101
6 201
6 301
6 401
7 1
7 101
7 201
7 301
7 401
8 1
8 101
8 201
8 301
8 401
9 1
9 101
9 201
9 301
9 401
10 1
10 101
10 201
10 301
10 401
11 1
11 10...

result:

ok 1256 lines

Test #3:

score: 0
Accepted
time: 187ms
memory: 94588kb

input:

500 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

5
1 1
1 101
1 201
1 301
1 401

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 4ms
memory: 70920kb

input:

1 1
1
3 3
1 1 1
1 1 1
1 1 1

output:

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 9ms
memory: 69772kb

input:

1 1
2
2 4
1 1 2 2
1 3 2 3

output:

3
1 3
1 4
2 3

result:

ok 4 lines

Test #6:

score: 0
Accepted
time: 3ms
memory: 69992kb

input:

1 1
1
4 1
1
4
2
6

output:

1
1 1

result:

ok 2 lines

Test #7:

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

input:

1 1
1
3 3
1 1 1
1 1 1
1 1 1

output:

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

result:

ok 10 lines

Test #8:

score: 0
Accepted
time: 7ms
memory: 70228kb

input:

2 2
1 3
0 0
1 3
1 2 3

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 7ms
memory: 70348kb

input:

1 4
4 4 4 1
1 1
2

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 3ms
memory: 69484kb

input:

1 1
0
6 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

output:

24
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4

result:

ok 25 lines

Test #11:

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

input:

1 1
2
1 5
3 2 3 3 2

output:

2
1 2
1 5

result:

ok 3 lines

Test #12:

score: 0
Accepted
time: 4ms
memory: 70292kb

input:

1 1
3
2 8
7 2 6 3 7 2 5 3
1 5 3 4 1 3 3 6

output:

5
1 4
1 8
2 3
2 6
2 7

result:

ok 6 lines

Test #13:

score: 0
Accepted
time: 4ms
memory: 71020kb

input:

2 3
1 1 0
1 1 0
1 7
1 1 1 1 1 1 1

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 4ms
memory: 70408kb

input:

2 2
0 1
2 2
9 3
2 3 2
1 1 1
1 3 2
1 1 1
1 2 2
3 3 3
1 1 3
1 3 3
1 3 1

output:

1
4 2

result:

ok 2 lines

Test #15:

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

input:

1 1
2
4 3
5 6 5
3 2 4
1 2 4
7 3 5

output:

2
2 2
3 2

result:

ok 3 lines

Test #16:

score: 0
Accepted
time: 9ms
memory: 70848kb

input:

5 4
1 0 1 1
0 0 1 0
1 0 0 1
1 0 0 0
0 0 1 1
3 1
1
1
1

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 3ms
memory: 69524kb

input:

4 2
3 0
0 0
1 2
3 2
1 4
1 1 1 2

output:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 9ms
memory: 69820kb

input:

8 8
0 2 3 6 5 3 5 2
6 5 6 5 3 2 0 5
2 1 5 3 0 0 4 2
2 0 7 2 3 5 3 7
5 1 4 6 0 5 6 7
3 0 1 0 5 4 5 7
3 4 6 1 5 3 3 1
3 6 7 3 6 1 5 5
4 4
7 7 3 7
2 4 5 3
6 3 1 1
3 7 2 1

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 4ms
memory: 70244kb

input:

1 1
61
4 1
52
48
40
46

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 11ms
memory: 70928kb

input:

1 1
1
95 86
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

8170
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

result:

ok 8171 lines

Test #21:

score: 0
Accepted
time: 4ms
memory: 69252kb

input:

1 1
2
6 96
3 2 1 2 1 1 3 2 1 2 2 3 1 3 3 3 3 2 2 1 1 2 2 3 2 1 1 2 2 1 1 3 1 3 1 3 2 3 3 1 3 2 3 3 3 3 3 1 1 1 2 2 3 2 3 3 3 1 3 3 2 1 1 1 1 2 2 2 1 2 2 3 2 1 3 2 1 3 3 3 3 2 3 1 1 3 2 2 2 2 1 2 2 2 1 1
1 2 3 2 2 3 2 2 3 1 2 2 3 3 2 3 2 1 1 1 3 1 3 3 3 2 3 2 3 3 3 3 1 1 3 2 2 1 3 1 1 3 1 1 3 2 1 3 3...

output:

191
1 2
1 4
1 8
1 10
1 11
1 18
1 19
1 22
1 23
1 25
1 28
1 29
1 37
1 42
1 51
1 52
1 54
1 61
1 66
1 67
1 68
1 70
1 71
1 73
1 76
1 82
1 87
1 88
1 89
1 90
1 92
1 93
1 94
2 2
2 4
2 5
2 7
2 8
2 11
2 12
2 15
2 17
2 26
2 28
2 36
2 37
2 46
2 54
2 60
2 61
2 62
2 64
2 66
2 70
2 75
2 76
2 80
2 81
2 84
2 86
2 87...

result:

ok 192 lines

Test #22:

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

input:

1 1
6
80 23
5 3 7 7 4 5 3 3 7 6 3 3 6 1 4 6 5 7 2 6 2 5 6
2 1 4 5 1 6 6 2 1 1 5 1 1 3 5 6 5 7 4 7 4 4 2
7 1 5 1 2 1 1 4 3 3 4 3 2 1 6 1 1 6 7 5 4 7 1
7 4 6 3 7 7 2 5 1 7 5 3 4 3 6 2 2 2 3 3 1 2 5
7 7 4 5 7 7 5 1 2 2 6 6 4 6 1 2 4 1 5 6 1 7 4
3 1 3 2 5 3 1 7 2 6 4 2 2 6 5 4 2 1 5 1 3 6 7
1 3 6 7 4 4 ...

output:

277
1 10
1 13
1 16
1 20
1 23
2 6
2 7
2 16
3 15
3 18
4 3
4 15
5 11
5 12
5 14
5 20
6 10
6 14
6 22
7 3
7 8
7 12
7 14
7 16
8 13
8 23
9 1
9 3
9 14
9 21
10 3
10 12
10 14
10 15
10 21
11 1
11 5
11 9
11 13
11 20
12 9
12 18
13 7
13 8
13 12
13 18
13 19
13 21
14 16
14 19
15 5
15 14
17 2
17 12
17 19
17 23
18 4
1...

result:

ok 278 lines

Test #23:

score: 0
Accepted
time: 4ms
memory: 71144kb

input:

1 3
94 82 89
4 2
32 23
91 15
19 42
54 45

output:

0

result:

ok single line: '0'

Test #24:

score: 0
Accepted
time: 3ms
memory: 69848kb

input:

1 4
0 0 1 0
65 88
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

5525
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

result:

ok 5526 lines

Test #25:

score: 0
Accepted
time: 3ms
memory: 69532kb

input:

1 3
2 0 3
1 30
3 3 2 2 3 1 3 2 2 3 2 3 2 3 1 1 2 2 2 3 3 1 3 3 1 1 1 1 1 2

output:

4
1 3
1 8
1 18
1 19

result:

ok 5 lines

Test #26:

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

input:

3 2
7 5
4 1
4 7
64 67
7 5 7 3 2 6 4 5 1 6 7 7 2 6 5 2 4 7 6 4 5 3 2 5 5 4 7 2 6 5 1 3 6 2 7 2 6 5 1 3 3 2 1 4 4 1 2 7 2 3 5 5 6 1 6 6 6 4 1 3 2 6 3 5 3 3 1
4 1 5 3 6 4 6 6 4 5 7 2 4 1 3 2 1 7 2 1 5 6 4 4 4 5 6 1 2 2 7 7 1 6 3 4 3 4 4 7 5 7 7 1 1 7 1 3 7 5 5 3 1 1 2 1 6 5 7 2 1 4 5 7 7 1 6
7 5 3 7 4 ...

output:

0

result:

ok single line: '0'

Test #27:

score: 0
Accepted
time: 7ms
memory: 69480kb

input:

3 5
0 0 1 1 1
0 1 0 0 0
1 1 0 1 0
6 7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

output:

12
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
4 1
4 2
4 3

result:

ok 13 lines

Test #28:

score: 0
Accepted
time: 3ms
memory: 70336kb

input:

6 1
3
0
1
3
0
2
6 2
2 3
3 2
2 3
3 3
3 3
1 3

output:

0

result:

ok single line: '0'

Test #29:

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

input:

1 8
7 3 3 7 7 5 7 1
2 2
3 7
2 1

output:

0

result:

ok single line: '0'

Test #30:

score: 0
Accepted
time: 3ms
memory: 69364kb

input:

1 1
48
4 8
74 75 78 99 58 26 87 45
82 29 80 61 15 66 58 15
55 44 92 11 71 50 95 36
36 7 45 91 83 16 49 87

output:

0

result:

ok single line: '0'

Test #31:

score: 0
Accepted
time: 4ms
memory: 70496kb

input:

1 2
99 39
9 8
75 76 86 25 25 64 90 78
71 58 5 18 93 14 47 92
68 9 5 97 52 33 99 48
68 74 82 67 34 58 81 75
53 9 30 47 49 42 5 11
84 2 44 86 30 81 83 9
27 88 19 17 99 47 23 40
58 95 1 3 79 99 77 45
76 19 37 12 91 96 77 3

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 3ms
memory: 69740kb

input:

1 7
68 51 66 68 68 26 96
1 4
51 25 71 18

output:

0

result:

ok single line: '0'

Test #33:

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

input:

5 5
1 1 1 0 0
0 1 1 0 1
1 1 1 1 0
1 0 0 0 0
1 0 1 1 1
94 95
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

8190
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

result:

ok 8191 lines

Test #34:

score: 0
Accepted
time: 8ms
memory: 70036kb

input:

2 1
1
3
20 27
3 3 1 2 1 1 2 1 2 2 3 1 2 2 3 2 3 3 2 2 2 1 3 3 3 3 1
2 1 2 2 3 1 1 2 3 2 2 2 3 1 2 1 1 1 3 3 1 2 2 3 1 2 2
1 2 2 1 2 3 2 3 2 2 2 2 1 1 1 3 2 1 2 3 1 2 3 1 2 3 3
1 2 3 3 3 3 1 1 1 2 1 1 3 2 2 1 2 2 2 2 2 2 1 1 1 1 3
2 1 1 2 1 3 3 3 3 1 3 1 3 1 3 3 1 3 2 2 3 3 2 1 1 1 1
1 1 2 3 1 1 2 2 ...

output:

53
1 5
2 6
2 16
3 4
3 13
4 7
4 8
4 9
4 11
4 16
5 10
5 14
6 5
6 9
6 18
6 24
7 1
7 2
7 19
8 3
8 11
9 17
9 19
10 6
10 7
10 24
10 26
11 15
12 7
12 20
12 21
12 23
13 14
13 17
14 3
14 12
14 16
14 23
15 9
15 10
16 8
16 13
16 17
17 4
17 11
17 18
17 25
18 2
18 19
18 20
19 3
19 18
19 24

result:

ok 54 lines

Test #35:

score: 0
Accepted
time: 8ms
memory: 69976kb

input:

3 9
7 5 4 2 1 3 3 5 5
1 4 3 1 7 5 5 1 3
2 0 2 1 1 4 6 7 6
41 80
7 7 1 4 2 6 1 7 7 6 2 5 2 3 6 7 5 7 2 3 2 3 6 6 5 5 1 1 1 4 7 1 2 7 5 5 7 3 1 4 4 2 3 6 4 1 1 3 7 2 4 1 7 2 1 1 6 6 6 6 6 2 4 1 2 4 5 6 4 3 3 3 4 3 6 7 5 7 5 1
6 4 7 1 2 5 4 5 4 5 3 4 2 3 4 2 4 1 6 2 2 6 5 6 6 6 6 5 7 2 4 4 5 3 5 2 3 5 ...

output:

0

result:

ok single line: '0'

Test #36:

score: 0
Accepted
time: 4ms
memory: 69872kb

input:

1 1
99
27 18
57 43 97 16 60 6 4 21 17 94 49 51 22 17 79 36 33 27
75 19 92 33 2 14 37 55 94 57 73 77 78 1 5 24 59 15
56 16 33 93 90 40 62 11 61 50 17 91 92 46 52 12 74 3
42 17 19 58 59 9 27 14 3 72 75 33 23 99 54 57 71 40
26 13 17 59 45 3 50 92 1 62 88 82 60 9 13 96 52 35
69 84 44 48 21 22 5 92 25 87...

output:

3
4 14
8 2
20 12

result:

ok 4 lines

Test #37:

score: 0
Accepted
time: 10ms
memory: 70828kb

input:

3 2
27 0
79 43
54 33
98 77
54 63 1 12 92 2 15 42 69 46 7 26 84 26 48 30 61 22 31 43 80 99 19 60 31 3 61 9 32 33 56 63 10 38 71 80 43 4 91 52 14 99 87 51 88 66 75 91 95 95 38 92 16 11 29 36 70 92 42 75 23 41 36 32 80 38 4 89 75 61 89 54 47 68 74 22 71
34 11 94 94 42 21 86 79 43 34 43 8 64 14 79 47 93...

output:

0

result:

ok single line: '0'

Test #38:

score: 0
Accepted
time: 3ms
memory: 69700kb

input:

4 3
95 37 42
65 85 10
95 70 41
34 53 50
3 8
53 48 45 44 65 15 33 28
59 9 47 75 6 49 16 38
38 58 87 24 11 64 73 11

output:

0

result:

ok single line: '0'

Test #39:

score: 0
Accepted
time: 3ms
memory: 69796kb

input:

8 6
67 89 13 10 95 5
74 12 75 73 12 81
65 54 20 61 3 5
45 93 13 88 30 54
84 40 22 15 5 18
67 13 67 41 70 32
49 60 3 78 71 79
64 91 14 22 97 47
88 48
10 13 33 90 93 45 89 71 10 17 18 11 11 43 53 24 81 35 17 13 68 61 68 62 60 32 91 43 50 71 87 39 23 10 44 64 56 48 85 57 55 33 12 32 6 68 3 94
41 97 5 8...

output:

0

result:

ok single line: '0'

Test #40:

score: 0
Accepted
time: 195ms
memory: 94500kb

input:

100 100
0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0
0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 ...

output:

160801
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok 160802 lines

Test #41:

score: 0
Accepted
time: 182ms
memory: 93500kb

input:

250 250
1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 ...

output:

63001
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 6...

result:

ok 63002 lines

Test #42:

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

input:

500 500
0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 1 ...

output:

1
1 1

result:

ok 2 lines

Extra Test:

score: 0
Extra Test Passed