QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385803#5107. Mosaic BrowsingUFRJAC ✓77ms43660kbC++203.9kb2024-04-11 07:25:172024-04-11 07:25:17

Judging History

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

  • [2024-04-11 07:25:17]
  • 评测
  • 测评结果:AC
  • 用时:77ms
  • 内存:43660kb
  • [2024-04-11 07:25:17]
  • 提交

answer

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = long long;
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
using namespace std;

template <typename dbl> struct cplx { ///start-hash
	dbl x, y; using P = cplx;
	cplx(dbl x_ = 0, dbl y_ = 0) : x(x_), y(y_) { }
	friend P operator+(P a, P b) { return P(a.x+b.x, a.y+b.y); }
	friend P operator-(P a, P b) { return P(a.x-b.x, a.y-b.y); }
	friend P operator*(P a, P b) { return P(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
	friend P conj(P a) { return P(a.x, -a.y); }
	friend P inv(P a) { dbl n = (a.x*a.x+a.y*a.y); return P(a.x/n,-a.y/n); }
};
template <typename T> struct root_of_unity {};
template <typename dbl> struct root_of_unity<cplx<dbl>> {
	static cplx<dbl> f(int k) {
		static const dbl PI = acos(-1); dbl a = 2*PI/k;
		return cplx<dbl>(cos(a),sin(a));
	}
}; ///end-hash
inline int nxt_pow2(int s) { return 1 << (s > 1 ? 32 - __builtin_clz(s-1) : 0); }
template<typename T> struct FFT {
	vector<T> rt; vector<int> rev;
	FFT() : rt(2, T(1)) {}
	void init(int N) {///start-hash
		N = nxt_pow2(N);
		if (N > int(rt.size())) {
			rev.resize(N); rt.reserve(N);
			for (int a = 0; a < N; ++a)
				rev[a] = (rev[a/2] | ((a&1)*N)) >> 1;
			for (int k = int(rt.size()); k < N; k *= 2) {
				rt.resize(2*k);
				T z = root_of_unity<T>::f(2*k);
				for (int a = k/2; a < k; ++a)
					rt[2*a] = rt[a], rt[2*a+1] = rt[a] * z;
			}
		}
	}///end-hash
	void fft(vector<T>& xs, bool inverse) const {///start-hash
		int N = int(xs.size());
		int s = __builtin_ctz(int(rev.size())/N);
		if (inverse) reverse(xs.begin() + 1, xs.end());
		for (int a = 0; a < N; ++a) {
			if (a < (rev[a] >> s)) swap(xs[a], xs[rev[a] >> s]);
		}
		for (int k = 1; k < N; k *= 2) {
			for (int a = 0; a < N; a += 2*k) {
				int u = a, v = u + k;
				for (int b = 0; b < k; ++b, ++u, ++v) {
					T z = rt[b + k] * xs[v];
					xs[v] = xs[u] - z, xs[u] = xs[u] + z;
				}
			}
		}
		if (inverse)
			for (int a = 0; a < N; ++a) xs[a] = xs[a] * inv(T(N));
	}///end-hash
	vector<T> convolve(vector<T> as, vector<T> bs) {///start-hash
		int N = int(as.size()), M = int(bs.size());
		int K = N + M - 1, S = nxt_pow2(K); init(S);
		if (min(N, M) <= 64) {
			vector<T> res(K);
			for (int u = 0; u < N; ++u) for (int v = 0; v < M; ++v)
				res[u + v] = res[u + v] + as[u] * bs[v];
			return res;
		} else {
			as.resize(S), bs.resize(S);
			fft(as, false); fft(bs, false);
			for (int i = 0; i < S; ++i) as[i] = as[i] * bs[i];
			fft(as, true); as.resize(K); return as;
		}
	}///end-hash
};

using dbl = double;
FFT<cplx<dbl>>fft;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n1, m1, n2, m2;
    cin>>n1>>m1;
    vector<vector<int>>a(n1, vector<int>(m1));
    for(int i=0;i<n1;i++){
        for(int j=0;j<m1;j++) cin>>a[i][j], a[i][j]--;
    }
    cin>>n2>>m2;
    vector<vector<int>>b(n2, vector<int>(m2));
    for(int i=0;i<n2;i++){
        for(int j=0;j<m2;j++) cin>>b[i][j], b[i][j]--;
    }
    if(n1 > n2 || m1 > m2){
        cout<<"0\n";
        return 0;
    }
    vector<cplx<dbl>>c(m2 * n1), d(m2 * n2);
    int t = 0;
    for(int i=0;i<n1;i++){
        for(int j=0;j<m1;j++){
            if(a[i][j] == -1) c[m2 * i + j] = cplx<dbl>(0, 0);
            else c[m2 * i + j] = cplx<dbl>(cos(a[i][j]), -sin(a[i][j])), t++;
        }
    }
    for(int i=0;i<n2;i++){
        for(int j=0;j<m2;j++){
            d[m2 * i + j] = cplx<dbl>(cos(b[i][j]), sin(b[i][j]));
        }
    }
    reverse(c.begin(), c.end());
    auto res = fft.convolve(c, d);
    vector<pair<int, int>>ans;
    for(int i=0;i<=n2-n1;i++){
        for(int j=0;j<=m2-m1;j++){
            int id = i * m2 + j + (m2 * n1 - 1);
            if( abs(res[id].x - t) < 1e-8 ) ans.push_back({i, j});
        }
    }
    cout<<ans.size()<<"\n";
    for(auto [x, y] : ans) cout<<x+1<<" "<<y+1<<"\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 60ms
memory: 39576kb

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: 65ms
memory: 40796kb

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: 77ms
memory: 43016kb

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: 0ms
memory: 3908kb

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: 0ms
memory: 3996kb

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: 0ms
memory: 3772kb

input:

1 1
1
4 1
1
4
2
6

output:

1
1 1

result:

ok 2 lines

Test #7:

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

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: 0ms
memory: 3804kb

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: 0ms
memory: 3740kb

input:

1 4
4 4 4 1
1 1
2

output:

0

result:

ok single line: '0'

Test #10:

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

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: 0ms
memory: 4000kb

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: 0ms
memory: 4036kb

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: 0ms
memory: 3740kb

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: 0ms
memory: 3928kb

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: 0ms
memory: 4040kb

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: 0ms
memory: 3652kb

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: 0ms
memory: 3692kb

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: 0ms
memory: 3816kb

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: 0ms
memory: 3816kb

input:

1 1
61
4 1
52
48
40
46

output:

0

result:

ok single line: '0'

Test #20:

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

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: 0ms
memory: 3928kb

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: 1ms
memory: 4176kb

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: 0ms
memory: 3688kb

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: 2ms
memory: 4160kb

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: 0ms
memory: 3812kb

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: 1ms
memory: 3980kb

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: 0ms
memory: 3860kb

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: 0ms
memory: 3996kb

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: 0ms
memory: 3872kb

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: 0ms
memory: 4040kb

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: 0ms
memory: 3788kb

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: 0ms
memory: 3652kb

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: 2ms
memory: 4556kb

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: 0ms
memory: 4124kb

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: 1ms
memory: 4044kb

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: 0ms
memory: 4000kb

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: 1ms
memory: 4404kb

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: 0ms
memory: 3672kb

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: 1ms
memory: 4028kb

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: 75ms
memory: 39576kb

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: 69ms
memory: 40872kb

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: 70ms
memory: 43660kb

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