QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#68521#5107. Mosaic Browsingnocriz#AC ✓3818ms242640kbC++204.5kb2022-12-16 23:03:512022-12-16 23:03:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-16 23:03:53]
  • 评测
  • 测评结果:AC
  • 用时:3818ms
  • 内存:242640kb
  • [2022-12-16 23:03:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
/**
 * Author: chilli
 * Date: 2019-04-16
 * License: CC0
 * Source: based on KACTL's FFT
 * Description: ntt(a) computes $\hat f(k) = \sum_x a[x] g^{xk}$ for all $k$, where $g=\text{root}^{(mod-1)/N}$.
 * N must be a power of 2.
 * Useful for convolution modulo specific nice primes of the form $2^a b+1$,
 * where the convolution result has size at most $2^a$. For arbitrary modulo, see FFTMod.
   \texttt{conv(a, b) = c}, where $c[x] = \sum a[i]b[x-i]$.
   For manual convolution: NTT the inputs, multiply
   pointwise, divide by n, reverse(start+1, end), NTT back.
 * Inputs must be in [0, mod).
 * Time: O(N \log N)
 * Status: stress-tested
 */
const ll mod = (119 << 23) + 1, root = 62; // = 998244353
ll add(ll a, ll b) { return a+b>=mod ? a+b-mod : a+b; }
ll mul(ll a, ll b) { return a*b%mod; }
ll modpow(ll b, ll e) {
    ll ans = 1;
    for (; e; b = b * b % mod, e /= 2)
        if (e & 1) ans = ans * b % mod;
    return ans;
}

// For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
// and 483 << 21 (same root). The last two are > 10^9.
typedef vector<ll> vl;
void ntt(vl &a) {
    int n = sz(a), L = 31 - __builtin_clz(n);
    static vl rt(2, 1);
    for (static int k = 2, s = 2; k < n; k *= 2, s++) {
        rt.resize(n);
        ll z[] = {1, modpow(root, mod >> s)};
        rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
    }
    vi rev(n);
    rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
    rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k *= 2)
        for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
            ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
            a[i + j + k] = ai - z + (z > ai ? mod : 0);
            ai += (ai + z >= mod ? z - mod : z);
        }
}

vl conv(const vl &a, const vl &b) {
    if (a.empty() || b.empty()) return {};
    int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B;
    int inv = modpow(n, mod - 2);
    vl L(a), R(b), out(n);
    L.resize(n), R.resize(n);
    ntt(L), ntt(R);
    rep(i,0,n) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
    ntt(out);
    return {out.begin(), out.begin() + s};
}

mt19937 rng(192755222);
const int N = 2048;
int mp[202];
bitset<N> good[N];

vl to_poly(vector<vi> vec) {
    assert(sz(vec) > 0);
    int n = sz(vec), m = sz(vec[0]);
    vl ans(N*N);
    rep(i, 0, n) rep(j, 0, m) {
        ans[i*N+j] = mp[vec[i][j]];
    }
    while(ans.back() == 0) ans.pop_back();
    return ans;
}

vl to_poly_rev(vector<vi> vec) {
    assert(sz(vec) > 0);
    int n = sz(vec), m = sz(vec[0]);
    vl ans(N*N);
    rep(i, 0, n) rep(j, 0, m) {
        ans[(N/2-i)*N+(N/2-j)] = mp[vec[i][j]];
    }
    while(ans.back() == 0) ans.pop_back();
    return ans;
}

int main() {
    int n, m, p, q;
    scanf("%d%d", &n, &m);
    vector<vi> a(n, vector<int>(m));
    for(auto &vec: a) {
        for(auto &v: vec) {
            scanf("%d", &v);
        }
    }

    scanf("%d%d", &p, &q);
    vector<vi> b(p, vector<int>(q));
    for(auto &vec: b) {
        for(auto &v: vec) {
            scanf("%d", &v);
        }
    }

    for(int i = 0; i < p-n+1; i++) {
        for(int j = 0; j < q-m+1; j++) {
            good[i][j] = true;
        }
    }
    
    rep(_, 0, 4) {
        mp[0] = 0;
        for(int i = 1; i < 202; i++) {
            mp[i] = rng() % mod;
        }
        vl A = to_poly_rev(a), B = to_poly(b);
        debug(sz(A), sz(B));
        
        ll sqr = 0;
        for(auto g: A) sqr = add(sqr, mul(g, g));

        vl C = conv(A, B);
        // debug(C);
        // debug(A,B,C);
        for(int i = 0; i < sz(C); i++) {
            int x = i / N - (N/2), y = i % N - (N/2);
            if(x >= 0 && y >= 0 && x < p-n+1 && y < q-m+1) {
                debug(x,y,C[i]);
                good[x][y] = good[x][y] && (C[i] == sqr);
            }
        }
    }

    vector<pii> ans;
    for(int i = 0; i < p-n+1; i++) {
        for(int j = 0; j < q-m+1; j++) if(good[i][j]) {
            ans.emplace_back(i, j);
        }
    }
    
    cout << sz(ans) << '\n';
    for(auto [i,j]: ans) {
        cout << i+1 << ' ' << j+1 << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3493ms
memory: 241740kb

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: 3547ms
memory: 241816kb

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: 3646ms
memory: 241884kb

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: 2386ms
memory: 216180kb

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: 2515ms
memory: 216156kb

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: 2236ms
memory: 216184kb

input:

1 1
1
4 1
1
4
2
6

output:

1
1 1

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 2448ms
memory: 216208kb

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: 2481ms
memory: 216268kb

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: 2417ms
memory: 216188kb

input:

1 4
4 4 4 1
1 1
2

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 59ms
memory: 68868kb

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: 2453ms
memory: 216152kb

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: 2522ms
memory: 216296kb

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: 2535ms
memory: 216344kb

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: 2468ms
memory: 232672kb

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: 2417ms
memory: 216392kb

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: 2507ms
memory: 216388kb

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: 2489ms
memory: 216164kb

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: 2689ms
memory: 216388kb

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: 2292ms
memory: 216208kb

input:

1 1
61
4 1
52
48
40
46

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 2852ms
memory: 233892kb

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: 2907ms
memory: 216496kb

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: 2732ms
memory: 234032kb

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: 2433ms
memory: 216388kb

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: 2892ms
memory: 233740kb

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: 2662ms
memory: 216156kb

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: 2981ms
memory: 233648kb

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: 2697ms
memory: 216104kb

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: 2348ms
memory: 216292kb

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: 2604ms
memory: 216148kb

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: 2563ms
memory: 216256kb

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: 2694ms
memory: 232668kb

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: 2549ms
memory: 216276kb

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: 2960ms
memory: 234176kb

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: 2721ms
memory: 232780kb

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: 2961ms
memory: 233324kb

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: 2590ms
memory: 232944kb

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: 2964ms
memory: 234324kb

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: 2767ms
memory: 216328kb

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: 2919ms
memory: 233868kb

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: 3521ms
memory: 241812kb

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: 3641ms
memory: 241912kb

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: 3818ms
memory: 242640kb

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