Submission ID Problem Status Score Time Memory Code / Answer files User Submit time
#18619 #59. 猜字母王 Hexguesser Accepted 100 30102 ms 37588 K C++ 17 / 3.3 K HKSCF2023-022 2023-07-15 16:13:47
Show orginal code
#include <iostream>
#include <array>
#define ll long long

using namespace std;

string S, T;
ll n, q, s, z, cnt[6], B[6];
array<ll, 13> A[100000];
array<ll, 13> st[400000], tmp, X;

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = A[l];
        return;
    }
    ll mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    for (int i = 0; i < 6; ++i) {
        st[id][i] = max(st[id * 2][i], st[id * 2 + 1][i]);
    }
    for (int i = 6; i < 13; ++i) {
        st[id][i] = (st[id * 2][i] | st[id * 2 + 1][i]);
    }
    if (!st[id][12]) {
        for (int i = 0; i < 6; ++i) {
            if (st[id * 2][i + 6] && st[id * 2 + 1][i + 6]) {
                if (st[id * 2][i] != st[id * 2 + 1][i]) {
                    st[id][12] = 1;
                }
            } else if (st[id * 2][i + 6]) {
                if (st[id * 2][i] < st[id * 2 + 1][i]) {
                    st[id][12] = 1;
                }
            } else if (st[id * 2 + 1][i + 6]) {
                if (st[id * 2][i] > st[id * 2 + 1][i]) {
                    st[id][12] = 1;
                }
            }
        }
    }
}

array<ll, 13> query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql)
        return tmp;
    else if (ql <= l && r <= qr)
        return st[id];
    ll mid = (l + r) / 2;
    array<ll, 13> lch, rch, res;
    lch = query(id * 2, l, mid, ql, qr);
    rch = query(id * 2 + 1, mid + 1, r, ql, qr);
    for (int i = 0; i < 6; ++i) {
        res[i] = max(lch[i], rch[i]);
    }
    for (int i = 6; i < 13; ++i) {
        res[i] = (lch[i] | rch[i]);
    }
    if (!res[12]) {
        for (int i = 0; i < 6; ++i) {
            if (lch[i + 6] && rch[i + 6]) {
                if (lch[i] != rch[i]) {
                    res[12] = 1;
                }
            } else if (lch[i + 6]) {
                if (lch[i] < rch[i]) {
                    res[12] = 1;
                }
            } else if (rch[i + 6]) {
                if (lch[i] > rch[i]) {
                    res[12] = 1;
                }
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> q;
    for (int i = 0; i < 13; ++i) tmp[i] = 0;
    for (int i = 0; i < n; ++i) {
        cin >> S >> T;
        for (int j = 0; j < 6; ++j) {
            cnt[j] = 0;
            B[j] = 0;
        }
        for (int j = 0; j < 6; ++j) {
            if (T[j] == 'x') {
                B[S[j] - 'a'] = 1;
            } else {
                ++cnt[S[j] - 'a'];
            }
        }
        for (int j = 0; j < 6; ++j) {
            A[i][j] = cnt[j];
        }
        for (int j = 0; j < 6; ++j) {
            A[i][j + 6] = B[j];
        }
        A[i][12] = 0;
    }
    build(1, 0, n - 1);
    ll l, r;
    while (q--) {
        cin >> l >> r;
        --l, --r;
        s = z = 0;
        X = query(1, 0, n - 1, l, r);
        for (int i = 0; i < 6; ++i) {
            cnt[i] = X[i];
            s += cnt[i];
            B[i] = X[i + 6];
            z += B[i];
        }
        if (s > 6 || (z == 6 && s != 6) || X[12]) {
            cout << "-1\n";
            continue;
        } else if (s == 6) {
            cout << "6\n";
            continue;
        } else if (z >= 5) {
            cout << "6\n";
            continue;
        }
        cout << s << '\n';
    }
}
Subtask #1
Accepted
Score: 8
Test case #1
Accepted
Score: 100
Time: 205 ms
Memory: 35688 KiB

Input file

84590 42147
aabbcb
ooxoxx
babbbc
xoxoxx
bbbabb
xoxoox
caaaca
xoxoxo
cbbaab
xxoooo
abcaac
ooxoox
acbc
<1678940 bytes omitted>

Output file

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

<84194 bytes omitted>

Your output

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

<84166 bytes omitted>

System message

Exited with return code 0
Test case #2
Accepted
Score: 100
Time: 105 ms
Memory: 35440 KiB

Input file

83386 7411
acbccb
xooxxo
aaacac
ooxoxx
babaca
ooooox
bcccab
oooxoo
aababb
xooxox
aabbbc
ooxooo
abbbc
<1254249 bytes omitted>

Output file

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

<14722 bytes omitted>

Your output

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

<14694 bytes omitted>

System message

Exited with return code 0
Test case #3
Accepted
Score: 100
Time: 187 ms
Memory: 35440 KiB

Input file

82181 39971
ccbacb
oxooox
cbabbc
oxooxo
acbbbb
ooxoxx
ccbcbc
ooxxox
bbbcab
oxxoox
accbac
ooooxx
bcca
<1619364 bytes omitted>

Output file

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

<79842 bytes omitted>

Your output

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

<79814 bytes omitted>

System message

Exited with return code 0
Test case #4
Accepted
Score: 100
Time: 367 ms
Memory: 37228 KiB

Input file

99997 100000
aaccbb
ooooox
caabac
ooxoxo
bbcbcc
oxoxoo
aabbcb
xoxooo
bbccaa
xoxoxo
bbbbcb
xxxxoo
bcc
<2578001 bytes omitted>

Output file

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

<199900 bytes omitted>

Your output

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

<199872 bytes omitted>

System message

Exited with return code 0
Test case #5
Accepted
Score: 100
Time: 354 ms
Memory: 37220 KiB

Input file

99999 99998
cacaca
oxooxo
abbcab
oxooox
ccbccc
xxooox
cbbbbb
ooxxox
cbcccc
xooxxo
bcaaca
oxooox
abac
<2578006 bytes omitted>

Output file

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4

<199896 bytes omitted>

Your output

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4
5
2
5
4
2
4
5
5
4
3
5
4
4
4

<199868 bytes omitted>

System message

Exited with return code 0
Subtask #2
Accepted
Score: 10
Test case #1
Accepted
Score: 100
Time: 205 ms
Memory: 35688 KiB

Input file

84590 42147
aabbcb
ooxoxx
babbbc
xoxoxx
bbbabb
xoxoox
caaaca
xoxoxo
cbbaab
xxoooo
abcaac
ooxoox
acbc
<1678940 bytes omitted>

Output file

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

<84194 bytes omitted>

Your output

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

<84166 bytes omitted>

System message

Exited with return code 0
Test case #2
Accepted
Score: 100
Time: 105 ms
Memory: 35440 KiB

Input file

83386 7411
acbccb
xooxxo
aaacac
ooxoxx
babaca
ooooox
bcccab
oooxoo
aababb
xooxox
aabbbc
ooxooo
abbbc
<1254249 bytes omitted>

Output file

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

<14722 bytes omitted>

Your output

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

<14694 bytes omitted>

System message

Exited with return code 0
Test case #3
Accepted
Score: 100
Time: 367 ms
Memory: 37228 KiB

Input file

99997 100000
aaccbb
ooooox
caabac
ooxoxo
bbcbcc
oxoxoo
aabbcb
xoxooo
bbccaa
xoxoxo
bbbbcb
xxxxoo
bcc
<2578001 bytes omitted>

Output file

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

<199900 bytes omitted>

Your output

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

<199872 bytes omitted>

System message

Exited with return code 0
Test case #4
Accepted
Score: 100
Time: 354 ms
Memory: 37220 KiB

Input file

99999 99998
cacaca
oxooxo
abbcab
oxooox
ccbccc
xxooox
cbbbbb
ooxxox
cbcccc
xooxxo
bcaaca
oxooox
abac
<2578006 bytes omitted>

Output file

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4

<199896 bytes omitted>

Your output

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4
5
2
5
4
2
4
5
5
4
3
5
4
4
4

<199868 bytes omitted>

System message

Exited with return code 0
Test case #5
Accepted
Score: 100
Time: 316 ms
Memory: 17388 KiB

Input file

36673 94424
fbefbf
xoxxox
cedcdf
xxoxox
cfcfba
xxxxxo
cbceda
xoxxoo
dadcda
oxoxox
eebaae
xxooxx
fded
<1589112 bytes omitted>

Output file

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

<188748 bytes omitted>

Your output

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

<188720 bytes omitted>

System message

Exited with return code 0
Test case #6
Accepted
Score: 100
Time: 137 ms
Memory: 17516 KiB

Input file

35469 26985
cbaeba
oxooxo
accfde
oxxooo
daebbf
oooxxo
bdddcf
xoxxoo
effaff
ooxoxx
acdfdc
oxxooo
aaba
<803588 bytes omitted>

Output file

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2

<53870 bytes omitted>

Your output

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2
4
4
4
3
4
3
3
2
3
2
4
3
3
4

<53842 bytes omitted>

System message

Exited with return code 0
Test case #7
Accepted
Score: 100
Time: 364 ms
Memory: 36200 KiB

Input file

88751 98586
aaacde
oxoxox
dcfdfc
oxxxxx
babdba
oooooo
fcedfe
xxxxxx
acffbb
oxxxoo
fecccd
xxxxxo
dacf
<2400756 bytes omitted>

Output file

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2

<197072 bytes omitted>

Your output

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2
3
1
3
4
2
3
1
4
3
3
2
2
2
3

<197044 bytes omitted>

System message

Exited with return code 0
Test case #8
Accepted
Score: 100
Time: 369 ms
Memory: 37228 KiB

Input file

99998 99997
fbcfcf
ooxxox
eccdde
xxxxoo
dfbcbe
ooxxoo
fffcaf
xoxxox
faacab
oxoxox
dafeaf
ooooxx
ccac
<2577652 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #9
Accepted
Score: 100
Time: 378 ms
Memory: 37228 KiB

Input file

99993 99997
fcbcea
xoooxo
edacfa
xoxoxo
bfccfd
oxooxo
cabbca
ooooxx
eacdee
xoooxx
dbcffa
oooxxo
ceae
<2577464 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #10
Accepted
Score: 100
Time: 10 ms
Memory: 252 KiB

Input file

4 4
abcdee
xxxxox
abcdee
oxxxxx
abcdee
xxxxxx
aabcde
oxxxxx
1 1
2 2
3 3
4 4

Output file

6
1
6
6

Your output

6
1
6
6

System message

Exited with return code 0
Test case #11
Accepted
Score: 100
Time: 8 ms
Memory: 256 KiB

Input file

1 1
abcdef
xxxxxx
1 1

Output file

-1

Your output

-1

System message

Exited with return code 0
Subtask #3
Accepted
Score: 19
Test case #1
Accepted
Score: 100
Time: 205 ms
Memory: 35688 KiB

Input file

84590 42147
aabbcb
ooxoxx
babbbc
xoxoxx
bbbabb
xoxoox
caaaca
xoxoxo
cbbaab
xxoooo
abcaac
ooxoox
acbc
<1678940 bytes omitted>

Output file

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

<84194 bytes omitted>

Your output

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

<84166 bytes omitted>

System message

Exited with return code 0
Test case #2
Accepted
Score: 100
Time: 105 ms
Memory: 35440 KiB

Input file

83386 7411
acbccb
xooxxo
aaacac
ooxoxx
babaca
ooooox
bcccab
oooxoo
aababb
xooxox
aabbbc
ooxooo
abbbc
<1254249 bytes omitted>

Output file

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

<14722 bytes omitted>

Your output

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

<14694 bytes omitted>

System message

Exited with return code 0
Test case #3
Accepted
Score: 100
Time: 367 ms
Memory: 37228 KiB

Input file

99997 100000
aaccbb
ooooox
caabac
ooxoxo
bbcbcc
oxoxoo
aabbcb
xoxooo
bbccaa
xoxoxo
bbbbcb
xxxxoo
bcc
<2578001 bytes omitted>

Output file

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

<199900 bytes omitted>

Your output

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

<199872 bytes omitted>

System message

Exited with return code 0
Test case #4
Accepted
Score: 100
Time: 354 ms
Memory: 37220 KiB

Input file

99999 99998
cacaca
oxooxo
abbcab
oxooox
ccbccc
xxooox
cbbbbb
ooxxox
cbcccc
xooxxo
bcaaca
oxooox
abac
<2578006 bytes omitted>

Output file

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4

<199896 bytes omitted>

Your output

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4
5
2
5
4
2
4
5
5
4
3
5
4
4
4

<199868 bytes omitted>

System message

Exited with return code 0
Test case #5
Accepted
Score: 100
Time: 316 ms
Memory: 17388 KiB

Input file

36673 94424
fbefbf
xoxxox
cedcdf
xxoxox
cfcfba
xxxxxo
cbceda
xoxxoo
dadcda
oxoxox
eebaae
xxooxx
fded
<1589112 bytes omitted>

Output file

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

<188748 bytes omitted>

Your output

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

<188720 bytes omitted>

System message

Exited with return code 0
Test case #6
Accepted
Score: 100
Time: 61 ms
Memory: 8812 KiB

Input file

17541 11593
bbcaac
oxoxoo
ccabac
ooxooo
bcbacb
xoxooo
ccabba
oooxox
babaca
xxooox
cbacab
ooxoox
bcca
<369890 bytes omitted>

Output file

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
<24894 bytes omitted>

Your output

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
5
4
3
2
-1
-1
5
3
5
3
4
5
4
<24866 bytes omitted>

System message

Exited with return code 0
Test case #7
Accepted
Score: 100
Time: 375 ms
Memory: 37376 KiB

Input file

99997 99992
baaabc
oxxxoo
cbcbab
oxxoxo
bbbbcc
xxooox
abaabb
xoxxxo
abccca
xoxoxx
bbbaaa
oxoxxx
cbab
<2577694 bytes omitted>

Output file

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

<216400 bytes omitted>

Your output

1
-1
3
3
4
3
3
2
2
-1
3
3
3
2
3
2
3
4
-1
2
2
3
3
-1
3
-1
3
3
-1
2
4
-1
3
3
-1
3
1
0
1
4
3
2
3
1
3
2
4
4
2
2
2
3
3
1
2
-1
3
3
3
3
<216372 bytes omitted>

System message

Exited with return code 0
Test case #8
Accepted
Score: 100
Time: 366 ms
Memory: 37228 KiB

Input file

99998 99993
babbcc
oxxxox
bcbabb
xooxxx
ccccab
xxoxxo
bcbbcc
xxooox
bbbbba
oxoxxx
aaacab
xxxoxo
abcc
<2577579 bytes omitted>

Output file

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
<217609 bytes omitted>

Your output

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
2
2
2
1
2
2
2
2
-1
2
1
2
-1
<217581 bytes omitted>

System message

Exited with return code 0
Test case #9
Accepted
Score: 100
Time: 7 ms
Memory: 376 KiB

Input file

14 7
aaaaaa
oooooo
aabbcc
ooxxxx
aaaaaa
ooooox
aabbbb
ooxxox
aabbcc
oxoxoo
bbbbcc
xoxoxo
aabbcc
oooo
<134 bytes omitted>

Output file

6
6
-1
4
-1
-1
-1

Your output

6
6
-1
4
-1
-1
-1

System message

Exited with return code 0
Subtask #4
Accepted
Score: 6
Test case #1
Accepted
Score: 100
Time: 8 ms
Memory: 256 KiB

Input file

2 2
aabbcc
oxoxox
dddeee
ooxxxx
1 1
1 2

Output file

3
6

Your output

3
6

System message

Exited with return code 0
Test case #2
Accepted
Score: 100
Time: 205 ms
Memory: 35688 KiB

Input file

84590 42147
aabbcb
ooxoxx
babbbc
xoxoxx
bbbabb
xoxoox
caaaca
xoxoxo
cbbaab
xxoooo
abcaac
ooxoox
acbc
<1678940 bytes omitted>

Output file

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

<84194 bytes omitted>

Your output

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

<84166 bytes omitted>

System message

Exited with return code 0
Test case #3
Accepted
Score: 100
Time: 105 ms
Memory: 35440 KiB

Input file

83386 7411
acbccb
xooxxo
aaacac
ooxoxx
babaca
ooooox
bcccab
oooxoo
aababb
xooxox
aabbbc
ooxooo
abbbc
<1254249 bytes omitted>

Output file

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

<14722 bytes omitted>

Your output

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

<14694 bytes omitted>

System message

Exited with return code 0
Test case #4
Accepted
Score: 100
Time: 367 ms
Memory: 37228 KiB

Input file

99997 100000
aaccbb
ooooox
caabac
ooxoxo
bbcbcc
oxoxoo
aabbcb
xoxooo
bbccaa
xoxoxo
bbbbcb
xxxxoo
bcc
<2578001 bytes omitted>

Output file

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

<199900 bytes omitted>

Your output

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

<199872 bytes omitted>

System message

Exited with return code 0
Test case #5
Accepted
Score: 100
Time: 354 ms
Memory: 37220 KiB

Input file

99999 99998
cacaca
oxooxo
abbcab
oxooox
ccbccc
xxooox
cbbbbb
ooxxox
cbcccc
xooxxo
bcaaca
oxooox
abac
<2578006 bytes omitted>

Output file

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4

<199896 bytes omitted>

Your output

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4
5
2
5
4
2
4
5
5
4
3
5
4
4
4

<199868 bytes omitted>

System message

Exited with return code 0
Test case #6
Accepted
Score: 100
Time: 316 ms
Memory: 17388 KiB

Input file

36673 94424
fbefbf
xoxxox
cedcdf
xxoxox
cfcfba
xxxxxo
cbceda
xoxxoo
dadcda
oxoxox
eebaae
xxooxx
fded
<1589112 bytes omitted>

Output file

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

<188748 bytes omitted>

Your output

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

<188720 bytes omitted>

System message

Exited with return code 0
Test case #7
Accepted
Score: 100
Time: 137 ms
Memory: 17516 KiB

Input file

35469 26985
cbaeba
oxooxo
accfde
oxxooo
daebbf
oooxxo
bdddcf
xoxxoo
effaff
ooxoxx
acdfdc
oxxooo
aaba
<803588 bytes omitted>

Output file

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2

<53870 bytes omitted>

Your output

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2
4
4
4
3
4
3
3
2
3
2
4
3
3
4

<53842 bytes omitted>

System message

Exited with return code 0
Test case #8
Accepted
Score: 100
Time: 364 ms
Memory: 36200 KiB

Input file

88751 98586
aaacde
oxoxox
dcfdfc
oxxxxx
babdba
oooooo
fcedfe
xxxxxx
acffbb
oxxxoo
fecccd
xxxxxo
dacf
<2400756 bytes omitted>

Output file

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2

<197072 bytes omitted>

Your output

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2
3
1
3
4
2
3
1
4
3
3
2
2
2
3

<197044 bytes omitted>

System message

Exited with return code 0
Test case #9
Accepted
Score: 100
Time: 369 ms
Memory: 37228 KiB

Input file

99998 99997
fbcfcf
ooxxox
eccdde
xxxxoo
dfbcbe
ooxxoo
fffcaf
xoxxox
faacab
oxoxox
dafeaf
ooooxx
ccac
<2577652 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #10
Accepted
Score: 100
Time: 378 ms
Memory: 37228 KiB

Input file

99993 99997
fcbcea
xoooxo
edacfa
xoxoxo
bfccfd
oxooxo
cabbca
ooooxx
eacdee
xoooxx
dbcffa
oooxxo
ceae
<2577464 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #11
Accepted
Score: 100
Time: 61 ms
Memory: 8812 KiB

Input file

17541 11593
bbcaac
oxoxoo
ccabac
ooxooo
bcbacb
xoxooo
ccabba
oooxox
babaca
xxooox
cbacab
ooxoox
bcca
<369890 bytes omitted>

Output file

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
<24894 bytes omitted>

Your output

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
5
4
3
2
-1
-1
5
3
5
3
4
5
4
<24866 bytes omitted>

System message

Exited with return code 0
Test case #12
Accepted
Score: 100
Time: 375 ms
Memory: 37376 KiB

Input file

99997 99992
baaabc
oxxxoo
cbcbab
oxxoxo
bbbbcc
xxooox
abaabb
xoxxxo
abccca
xoxoxx
bbbaaa
oxoxxx
cbab
<2577694 bytes omitted>

Output file

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

<216400 bytes omitted>

Your output

1
-1
3
3
4
3
3
2
2
-1
3
3
3
2
3
2
3
4
-1
2
2
3
3
-1
3
-1
3
3
-1
2
4
-1
3
3
-1
3
1
0
1
4
3
2
3
1
3
2
4
4
2
2
2
3
3
1
2
-1
3
3
3
3
<216372 bytes omitted>

System message

Exited with return code 0
Test case #13
Accepted
Score: 100
Time: 366 ms
Memory: 37228 KiB

Input file

99998 99993
babbcc
oxxxox
bcbabb
xooxxx
ccccab
xxoxxo
bcbbcc
xxooox
bbbbba
oxoxxx
aaacab
xxxoxo
abcc
<2577579 bytes omitted>

Output file

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
<217609 bytes omitted>

Your output

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
2
2
2
1
2
2
2
2
-1
2
1
2
-1
<217581 bytes omitted>

System message

Exited with return code 0
Test case #14
Accepted
Score: 100
Time: 260 ms
Memory: 34316 KiB

Input file

70828 65903
cedfca
ooxooo
abbfba
oxxoxx
fddfad
xxxoox
bcbcbb
ooxoxx
ebcdce
oxoxox
fbeeff
xxxooo
aebf
<1761814 bytes omitted>

Output file

6
1
5
5
4
3
3
4
4
4
4
3
-1
4
4
-1
4
4
6
-1
5
3
2
-1
3
1
4
-1
1
4
5
5
3
2
3
4
4
3
4
3
-1
-1
2
4
5
3
3
<140089 bytes omitted>

Your output

6
1
5
5
4
3
3
4
4
4
4
3
-1
4
4
-1
4
4
6
-1
5
3
2
-1
3
1
4
-1
1
4
5
5
3
2
3
4
4
3
4
3
-1
-1
2
4
5
3
3
2
3
1
4
1
3
-1
3
-1
4
4
3
-
<140061 bytes omitted>

System message

Exited with return code 0
Test case #15
Accepted
Score: 100
Time: 170 ms
Memory: 34192 KiB

Input file

69624 31167
cafeab
ooxoxo
afabfa
oxxoxx
baefbe
oooxxo
dfacfe
xxooxo
cfaaca
oxoxxo
cbddad
xoxxox
dabb
<1338647 bytes omitted>

Output file

3
-1
5
4
6
4
5
-1
4
3
4
5
4
3
5
4
4
2
5
3
4
-1
4
2
4
4
1
3
4
3
6
-1
3
4
5
6
2
4
6
4
4
4
-1
5
5
3
4
3
<66198 bytes omitted>

Your output

3
-1
5
4
6
4
5
-1
4
3
4
5
4
3
5
4
4
2
5
3
4
-1
4
2
4
4
1
3
4
3
6
-1
3
4
5
6
2
4
6
4
4
4
-1
5
5
3
4
3
2
4
-1
-1
5
4
4
3
2
6
3
3
-
<66170 bytes omitted>

System message

Exited with return code 0
Test case #16
Accepted
Score: 100
Time: 425 ms
Memory: 37492 KiB

Input file

99998 99999
cbeacb
oxxoox
deceaa
oxoxoo
ecaeef
xooxxo
bafafd
xoxooo
fdbbfd
xxxxoo
cccece
oxxxox
ccdc
<2577321 bytes omitted>

Output file

3
4
2
5
-1
4
5
5
4
3
4
6
3
3
2
1
6
6
-1
-1
4
3
3
2
-1
4
-1
4
4
3
6
5
6
-1
-1
6
4
5
-1
3
-1
5
-1
4
3

<212373 bytes omitted>

Your output

3
4
2
5
-1
4
5
5
4
3
4
6
3
3
2
1
6
6
-1
-1
4
3
3
2
-1
4
-1
4
4
3
6
5
6
-1
-1
6
4
5
-1
3
-1
5
-1
4
3
5
3
4
-1
4
-1
3
-1
4
3
-1
-1
<212345 bytes omitted>

System message

Exited with return code 0
Test case #17
Accepted
Score: 100
Time: 432 ms
Memory: 37480 KiB

Input file

99999 99997
cbbebc
oxxxxo
babfee
xoxxox
feabdc
xxxxoo
caaded
ooooxx
facada
xooooo
baeafd
xoxoxo
efea
<2577655 bytes omitted>

Output file

5
3
3
1
2
1
3
6
5
4
-1
3
5
3
3
3
2
3
3
2
2
3
1
-1
3
3
3
6
-1
-1
4
1
2
2
2
4
2
2
3
3
3
4
3
3
-1
-1
4

<212453 bytes omitted>

Your output

5
3
3
1
2
1
3
6
5
4
-1
3
5
3
3
3
2
3
3
2
2
3
1
-1
3
3
3
6
-1
-1
4
1
2
2
2
4
2
2
3
3
3
4
3
3
-1
-1
4
3
6
3
3
-1
6
3
-1
2
3
4
4
3

<212425 bytes omitted>

System message

Exited with return code 0
Test case #18
Accepted
Score: 100
Time: 407 ms
Memory: 37356 KiB

Input file

99994 99994
fddbbd
ooxoxo
ffbced
xxoooo
afbcfb
xoxoxo
dffffc
oxxoxo
fdeceb
ooooxo
dfccff
ooxoxx
bdab
<2577440 bytes omitted>

Output file

4
5
5
2
5
5
6
-1
4
3
2
4
2
4
3
3
4
6
3
5
4
3
2
-1
5
-1
-1
5
4
5
3
4
4
5
5
6
4
5
6
5
4
5
3
-1
5
5
4
5
<213092 bytes omitted>

Your output

4
5
5
2
5
5
6
-1
4
3
2
4
2
4
3
3
4
6
3
5
4
3
2
-1
5
-1
-1
5
4
5
3
4
4
5
5
6
4
5
6
5
4
5
3
-1
5
5
4
5
6
6
5
6
2
3
3
5
4
5
3
4
4
3
<213064 bytes omitted>

System message

Exited with return code 0
Test case #19
Accepted
Score: 100
Time: 377 ms
Memory: 37180 KiB

Input file

99999 99991
ffeafe
xxxoox
ddfccc
oxoxxo
becbbe
oxooox
cabbeb
ooxoxo
ccfabb
oxooox
bdbdbc
ooxxoo
ceba
<2577761 bytes omitted>

Output file

1
6
4
2
3
4
5
2
3
5
3
5
4
4
5
4
6
3
6
4
5
5
5
3
5
4
-1
5
3
-1
5
4
-1
6
6
3
4
5
2
-1
6
4
4
6
6
5
4
3

<213061 bytes omitted>

Your output

1
6
4
2
3
4
5
2
3
5
3
5
4
4
5
4
6
3
6
4
5
5
5
3
5
4
-1
5
3
-1
5
4
-1
6
6
3
4
5
2
-1
6
4
4
6
6
5
4
3
5
4
4
-1
5
5
2
5
4
4
3
4
6
3
<213033 bytes omitted>

System message

Exited with return code 0
Test case #20
Accepted
Score: 100
Time: 10 ms
Memory: 252 KiB

Input file

4 4
abcdee
xxxxox
abcdee
oxxxxx
abcdee
xxxxxx
aabcde
oxxxxx
1 1
2 2
3 3
4 4

Output file

6
1
6
6

Your output

6
1
6
6

System message

Exited with return code 0
Test case #21
Accepted
Score: 100
Time: 7 ms
Memory: 376 KiB

Input file

14 7
aaaaaa
oooooo
aabbcc
ooxxxx
aaaaaa
ooooox
aabbbb
ooxxox
aabbcc
oxoxoo
bbbbcc
xoxoxo
aabbcc
oooo
<134 bytes omitted>

Output file

6
6
-1
4
-1
-1
-1

Your output

6
6
-1
4
-1
-1
-1

System message

Exited with return code 0
Test case #22
Accepted
Score: 100
Time: 9 ms
Memory: 364 KiB

Input file

8 4
aaaaaa
ooooox
bcdeaa
xxxxoo
aaabbb
oooxxx
ccddee
xxxxxx
aaaaab
ooooox
ccddee
xxxxxx
aaaaab
ooooo
<32 bytes omitted>

Output file

6
3
5
6

Your output

6
3
5
6

System message

Exited with return code 0
Test case #23
Accepted
Score: 100
Time: 9 ms
Memory: 508 KiB

Input file

2 1
abcdef
oooooo
abcdee
oooooo
1 2

Output file

-1

Your output

-1

System message

Exited with return code 0
Test case #24
Accepted
Score: 100
Time: 8 ms
Memory: 256 KiB

Input file

1 1
abcdef
xxxxxx
1 1

Output file

-1

Your output

-1

System message

Exited with return code 0
Test case #25
Accepted
Score: 100
Time: 10 ms
Memory: 376 KiB

Input file

2 1
abcdef
xxxxxx
abcdef
xxxxxx
1 2

Output file

-1

Your output

-1

System message

Exited with return code 0
Subtask #5
Accepted
Score: 30
Test case #1
Accepted
Score: 100
Time: 8 ms
Memory: 256 KiB

Input file

2 2
aabbcc
oxoxox
dddeee
ooxxxx
1 1
1 2

Output file

3
6

Your output

3
6

System message

Exited with return code 0
Test case #2
Accepted
Score: 100
Time: 205 ms
Memory: 35688 KiB

Input file

84590 42147
aabbcb
ooxoxx
babbbc
xoxoxx
bbbabb
xoxoox
caaaca
xoxoxo
cbbaab
xxoooo
abcaac
ooxoox
acbc
<1678940 bytes omitted>

Output file

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

<84194 bytes omitted>

Your output

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

<84166 bytes omitted>

System message

Exited with return code 0
Test case #3
Accepted
Score: 100
Time: 105 ms
Memory: 35440 KiB

Input file

83386 7411
acbccb
xooxxo
aaacac
ooxoxx
babaca
ooooox
bcccab
oooxoo
aababb
xooxox
aabbbc
ooxooo
abbbc
<1254249 bytes omitted>

Output file

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

<14722 bytes omitted>

Your output

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

<14694 bytes omitted>

System message

Exited with return code 0
Test case #4
Accepted
Score: 100
Time: 367 ms
Memory: 37228 KiB

Input file

99997 100000
aaccbb
ooooox
caabac
ooxoxo
bbcbcc
oxoxoo
aabbcb
xoxooo
bbccaa
xoxoxo
bbbbcb
xxxxoo
bcc
<2578001 bytes omitted>

Output file

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

<199900 bytes omitted>

Your output

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

<199872 bytes omitted>

System message

Exited with return code 0
Test case #5
Accepted
Score: 100
Time: 354 ms
Memory: 37220 KiB

Input file

99999 99998
cacaca
oxooxo
abbcab
oxooox
ccbccc
xxooox
cbbbbb
ooxxox
cbcccc
xooxxo
bcaaca
oxooox
abac
<2578006 bytes omitted>

Output file

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4

<199896 bytes omitted>

Your output

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4
5
2
5
4
2
4
5
5
4
3
5
4
4
4

<199868 bytes omitted>

System message

Exited with return code 0
Test case #6
Accepted
Score: 100
Time: 316 ms
Memory: 17388 KiB

Input file

36673 94424
fbefbf
xoxxox
cedcdf
xxoxox
cfcfba
xxxxxo
cbceda
xoxxoo
dadcda
oxoxox
eebaae
xxooxx
fded
<1589112 bytes omitted>

Output file

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

<188748 bytes omitted>

Your output

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

<188720 bytes omitted>

System message

Exited with return code 0
Test case #7
Accepted
Score: 100
Time: 137 ms
Memory: 17516 KiB

Input file

35469 26985
cbaeba
oxooxo
accfde
oxxooo
daebbf
oooxxo
bdddcf
xoxxoo
effaff
ooxoxx
acdfdc
oxxooo
aaba
<803588 bytes omitted>

Output file

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2

<53870 bytes omitted>

Your output

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2
4
4
4
3
4
3
3
2
3
2
4
3
3
4

<53842 bytes omitted>

System message

Exited with return code 0
Test case #8
Accepted
Score: 100
Time: 364 ms
Memory: 36200 KiB

Input file

88751 98586
aaacde
oxoxox
dcfdfc
oxxxxx
babdba
oooooo
fcedfe
xxxxxx
acffbb
oxxxoo
fecccd
xxxxxo
dacf
<2400756 bytes omitted>

Output file

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2

<197072 bytes omitted>

Your output

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2
3
1
3
4
2
3
1
4
3
3
2
2
2
3

<197044 bytes omitted>

System message

Exited with return code 0
Test case #9
Accepted
Score: 100
Time: 369 ms
Memory: 37228 KiB

Input file

99998 99997
fbcfcf
ooxxox
eccdde
xxxxoo
dfbcbe
ooxxoo
fffcaf
xoxxox
faacab
oxoxox
dafeaf
ooooxx
ccac
<2577652 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #10
Accepted
Score: 100
Time: 378 ms
Memory: 37228 KiB

Input file

99993 99997
fcbcea
xoooxo
edacfa
xoxoxo
bfccfd
oxooxo
cabbca
ooooxx
eacdee
xoooxx
dbcffa
oooxxo
ceae
<2577464 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #11
Accepted
Score: 100
Time: 61 ms
Memory: 8812 KiB

Input file

17541 11593
bbcaac
oxoxoo
ccabac
ooxooo
bcbacb
xoxooo
ccabba
oooxox
babaca
xxooox
cbacab
ooxoox
bcca
<369890 bytes omitted>

Output file

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
<24894 bytes omitted>

Your output

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
5
4
3
2
-1
-1
5
3
5
3
4
5
4
<24866 bytes omitted>

System message

Exited with return code 0
Test case #12
Accepted
Score: 100
Time: 375 ms
Memory: 37376 KiB

Input file

99997 99992
baaabc
oxxxoo
cbcbab
oxxoxo
bbbbcc
xxooox
abaabb
xoxxxo
abccca
xoxoxx
bbbaaa
oxoxxx
cbab
<2577694 bytes omitted>

Output file

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

<216400 bytes omitted>

Your output

1
-1
3
3
4
3
3
2
2
-1
3
3
3
2
3
2
3
4
-1
2
2
3
3
-1
3
-1
3
3
-1
2
4
-1
3
3
-1
3
1
0
1
4
3
2
3
1
3
2
4
4
2
2
2
3
3
1
2
-1
3
3
3
3
<216372 bytes omitted>

System message

Exited with return code 0
Test case #13
Accepted
Score: 100
Time: 366 ms
Memory: 37228 KiB

Input file

99998 99993
babbcc
oxxxox
bcbabb
xooxxx
ccccab
xxoxxo
bcbbcc
xxooox
bbbbba
oxoxxx
aaacab
xxxoxo
abcc
<2577579 bytes omitted>

Output file

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
<217609 bytes omitted>

Your output

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
2
2
2
1
2
2
2
2
-1
2
1
2
-1
<217581 bytes omitted>

System message

Exited with return code 0
Test case #14
Accepted
Score: 100
Time: 260 ms
Memory: 34316 KiB

Input file

70828 65903
cedfca
ooxooo
abbfba
oxxoxx
fddfad
xxxoox
bcbcbb
ooxoxx
ebcdce
oxoxox
fbeeff
xxxooo
aebf
<1761814 bytes omitted>

Output file

6
1
5
5
4
3
3
4
4
4
4
3
-1
4
4
-1
4
4
6
-1
5
3
2
-1
3
1
4
-1
1
4
5
5
3
2
3
4
4
3
4
3
-1
-1
2
4
5
3
3
<140089 bytes omitted>

Your output

6
1
5
5
4
3
3
4
4
4
4
3
-1
4
4
-1
4
4
6
-1
5
3
2
-1
3
1
4
-1
1
4
5
5
3
2
3
4
4
3
4
3
-1
-1
2
4
5
3
3
2
3
1
4
1
3
-1
3
-1
4
4
3
-
<140061 bytes omitted>

System message

Exited with return code 0
Test case #15
Accepted
Score: 100
Time: 170 ms
Memory: 34192 KiB

Input file

69624 31167
cafeab
ooxoxo
afabfa
oxxoxx
baefbe
oooxxo
dfacfe
xxooxo
cfaaca
oxoxxo
cbddad
xoxxox
dabb
<1338647 bytes omitted>

Output file

3
-1
5
4
6
4
5
-1
4
3
4
5
4
3
5
4
4
2
5
3
4
-1
4
2
4
4
1
3
4
3
6
-1
3
4
5
6
2
4
6
4
4
4
-1
5
5
3
4
3
<66198 bytes omitted>

Your output

3
-1
5
4
6
4
5
-1
4
3
4
5
4
3
5
4
4
2
5
3
4
-1
4
2
4
4
1
3
4
3
6
-1
3
4
5
6
2
4
6
4
4
4
-1
5
5
3
4
3
2
4
-1
-1
5
4
4
3
2
6
3
3
-
<66170 bytes omitted>

System message

Exited with return code 0
Test case #16
Accepted
Score: 100
Time: 425 ms
Memory: 37492 KiB

Input file

99998 99999
cbeacb
oxxoox
deceaa
oxoxoo
ecaeef
xooxxo
bafafd
xoxooo
fdbbfd
xxxxoo
cccece
oxxxox
ccdc
<2577321 bytes omitted>

Output file

3
4
2
5
-1
4
5
5
4
3
4
6
3
3
2
1
6
6
-1
-1
4
3
3
2
-1
4
-1
4
4
3
6
5
6
-1
-1
6
4
5
-1
3
-1
5
-1
4
3

<212373 bytes omitted>

Your output

3
4
2
5
-1
4
5
5
4
3
4
6
3
3
2
1
6
6
-1
-1
4
3
3
2
-1
4
-1
4
4
3
6
5
6
-1
-1
6
4
5
-1
3
-1
5
-1
4
3
5
3
4
-1
4
-1
3
-1
4
3
-1
-1
<212345 bytes omitted>

System message

Exited with return code 0
Test case #17
Accepted
Score: 100
Time: 432 ms
Memory: 37480 KiB

Input file

99999 99997
cbbebc
oxxxxo
babfee
xoxxox
feabdc
xxxxoo
caaded
ooooxx
facada
xooooo
baeafd
xoxoxo
efea
<2577655 bytes omitted>

Output file

5
3
3
1
2
1
3
6
5
4
-1
3
5
3
3
3
2
3
3
2
2
3
1
-1
3
3
3
6
-1
-1
4
1
2
2
2
4
2
2
3
3
3
4
3
3
-1
-1
4

<212453 bytes omitted>

Your output

5
3
3
1
2
1
3
6
5
4
-1
3
5
3
3
3
2
3
3
2
2
3
1
-1
3
3
3
6
-1
-1
4
1
2
2
2
4
2
2
3
3
3
4
3
3
-1
-1
4
3
6
3
3
-1
6
3
-1
2
3
4
4
3

<212425 bytes omitted>

System message

Exited with return code 0
Test case #18
Accepted
Score: 100
Time: 407 ms
Memory: 37356 KiB

Input file

99994 99994
fddbbd
ooxoxo
ffbced
xxoooo
afbcfb
xoxoxo
dffffc
oxxoxo
fdeceb
ooooxo
dfccff
ooxoxx
bdab
<2577440 bytes omitted>

Output file

4
5
5
2
5
5
6
-1
4
3
2
4
2
4
3
3
4
6
3
5
4
3
2
-1
5
-1
-1
5
4
5
3
4
4
5
5
6
4
5
6
5
4
5
3
-1
5
5
4
5
<213092 bytes omitted>

Your output

4
5
5
2
5
5
6
-1
4
3
2
4
2
4
3
3
4
6
3
5
4
3
2
-1
5
-1
-1
5
4
5
3
4
4
5
5
6
4
5
6
5
4
5
3
-1
5
5
4
5
6
6
5
6
2
3
3
5
4
5
3
4
4
3
<213064 bytes omitted>

System message

Exited with return code 0
Test case #19
Accepted
Score: 100
Time: 377 ms
Memory: 37180 KiB

Input file

99999 99991
ffeafe
xxxoox
ddfccc
oxoxxo
becbbe
oxooox
cabbeb
ooxoxo
ccfabb
oxooox
bdbdbc
ooxxoo
ceba
<2577761 bytes omitted>

Output file

1
6
4
2
3
4
5
2
3
5
3
5
4
4
5
4
6
3
6
4
5
5
5
3
5
4
-1
5
3
-1
5
4
-1
6
6
3
4
5
2
-1
6
4
4
6
6
5
4
3

<213061 bytes omitted>

Your output

1
6
4
2
3
4
5
2
3
5
3
5
4
4
5
4
6
3
6
4
5
5
5
3
5
4
-1
5
3
-1
5
4
-1
6
6
3
4
5
2
-1
6
4
4
6
6
5
4
3
5
4
4
-1
5
5
2
5
4
4
3
4
6
3
<213033 bytes omitted>

System message

Exited with return code 0
Test case #20
Accepted
Score: 100
Time: 160 ms
Memory: 18284 KiB

Input file

42234 34548
baaaac
ooxxxx
abcbca
xoxoxo
acbcaa
xxoxxo
bacccc
ooxxxx
bccaba
oxxxoo
bcaaac
oxoxxx
abbc
<987843 bytes omitted>

Output file

-1
3
-1
3
3
3
3
-1
3
3
3
3
3
3
-1
3
-1
-1
3
-1
3
3
-1
3
3
3
3
3
3
-1
3
3
3
3
3
-1
3
3
-1
3
3
3
3
-1

<82054 bytes omitted>

Your output

-1
3
-1
3
3
3
3
-1
3
3
3
3
3
3
-1
3
-1
-1
3
-1
3
3
-1
3
3
3
3
3
3
-1
3
3
3
3
3
-1
3
3
-1
3
3
3
3
-1
3
3
3
-1
3
3
3
-1
3
3
-1
2
3
<82026 bytes omitted>

System message

Exited with return code 0
Test case #21
Accepted
Score: 100
Time: 116 ms
Memory: 36460 KiB

Input file

90012 9353
bbbbcc
xxxxoo
bbcbcb
xxoxox
abbaba
oxxxxo
bcbbac
xoxxoo
ccbacb
ooxoxx
babccc
xoxxoo
cccbc
<1369973 bytes omitted>

Output file

-1
4
-1
4
4
4
-1
-1
4
4
-1
-1
4
4
3
-1
4
4
4
4
-1
4
4
4
4
-1
4
4
4
-1
4
4
4
4
4
-1
-1
-1
4
-1
4
4
4

<22008 bytes omitted>

Your output

-1
4
-1
4
4
4
-1
-1
4
4
-1
-1
4
4
3
-1
4
4
4
4
-1
4
4
4
4
-1
4
4
4
-1
4
4
4
4
4
-1
-1
-1
4
-1
4
4
4
4
4
4
4
-1
4
-1
-1
-1
4
-1
4
<21980 bytes omitted>

System message

Exited with return code 0
Test case #22
Accepted
Score: 100
Time: 444 ms
Memory: 37232 KiB

Input file

99995 99992
bbbccc
xxxooo
acbcbc
ooxoxo
cbabca
oxoxoo
abcbca
oxoxoo
aaaabc
xxooxo
bbccbb
xxooxx
abca
<2577796 bytes omitted>

Output file

5
5
5
-1
-1
5
5
5
5
4
-1
-1
-1
5
5
-1
5
-1
5
5
5
-1
-1
4
5
5
5
5
-1
5
5
-1
-1
5
5
5
-1
5
5
-1
5
5
-1
<239463 bytes omitted>

Your output

5
5
5
-1
-1
5
5
5
5
4
-1
-1
-1
5
5
-1
5
-1
5
5
5
-1
-1
4
5
5
5
5
-1
5
5
-1
-1
5
5
5
-1
5
5
-1
5
5
-1
5
5
-1
5
5
5
5
-1
-1
-1
-1

<239435 bytes omitted>

System message

Exited with return code 0
Test case #23
Accepted
Score: 100
Time: 370 ms
Memory: 34664 KiB

Input file

73896 69983
caccbc
xoxoox
aabaaa
xoooxo
ccbaaa
xooooo
bacaab
xooooo
acbbac
oooxox
cbccab
xooxox
cbca
<1839239 bytes omitted>

Output file

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<139866 bytes omitted>

Your output

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<139838 bytes omitted>

System message

Exited with return code 0
Test case #24
Accepted
Score: 100
Time: 427 ms
Memory: 19652 KiB

Input file

56804 97814
aacaca
oooooo
bcaacb
xoooox
cacbcc
xooxxo
bccaac
xoxooo
acbbbc
ooxxxo
acccba
oxooxo
bcba
<1910183 bytes omitted>

Output file

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<195528 bytes omitted>

Your output

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<195500 bytes omitted>

System message

Exited with return code 0
Test case #25
Accepted
Score: 100
Time: 532 ms
Memory: 37588 KiB

Input file

99999 99994
baaabb
xxxoxx
ccbaca
ooxxoo
abcaba
xxoxxo
abcbba
oxoxxx
abcaab
xxooxx
aaaaac
xoxxxo
aaab
<2559863 bytes omitted>

Output file

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4

<199888 bytes omitted>

Your output

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4

<199860 bytes omitted>

System message

Exited with return code 0
Test case #26
Accepted
Score: 100
Time: 509 ms
Memory: 37228 KiB

Input file

99992 99995
caabba
oxxoxo
cccaab
oooxoo
bacbac
xoooxo
cbccbb
oxooox
acacab
xoxooo
cababb
oxxoxo
aaca
<2559852 bytes omitted>

Output file

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<199890 bytes omitted>

Your output

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<199862 bytes omitted>

System message

Exited with return code 0
Test case #27
Accepted
Score: 100
Time: 10 ms
Memory: 252 KiB

Input file

4 4
abcdee
xxxxox
abcdee
oxxxxx
abcdee
xxxxxx
aabcde
oxxxxx
1 1
2 2
3 3
4 4

Output file

6
1
6
6

Your output

6
1
6
6

System message

Exited with return code 0
Test case #28
Accepted
Score: 100
Time: 7 ms
Memory: 376 KiB

Input file

14 7
aaaaaa
oooooo
aabbcc
ooxxxx
aaaaaa
ooooox
aabbbb
ooxxox
aabbcc
oxoxoo
bbbbcc
xoxoxo
aabbcc
oooo
<134 bytes omitted>

Output file

6
6
-1
4
-1
-1
-1

Your output

6
6
-1
4
-1
-1
-1

System message

Exited with return code 0
Test case #29
Accepted
Score: 100
Time: 9 ms
Memory: 364 KiB

Input file

8 4
aaaaaa
ooooox
bcdeaa
xxxxoo
aaabbb
oooxxx
ccddee
xxxxxx
aaaaab
ooooox
ccddee
xxxxxx
aaaaab
ooooo
<32 bytes omitted>

Output file

6
3
5
6

Your output

6
3
5
6

System message

Exited with return code 0
Test case #30
Accepted
Score: 100
Time: 9 ms
Memory: 508 KiB

Input file

2 1
abcdef
oooooo
abcdee
oooooo
1 2

Output file

-1

Your output

-1

System message

Exited with return code 0
Test case #31
Accepted
Score: 100
Time: 8 ms
Memory: 256 KiB

Input file

1 1
abcdef
xxxxxx
1 1

Output file

-1

Your output

-1

System message

Exited with return code 0
Test case #32
Accepted
Score: 100
Time: 10 ms
Memory: 376 KiB

Input file

2 1
abcdef
xxxxxx
abcdef
xxxxxx
1 2

Output file

-1

Your output

-1

System message

Exited with return code 0
Subtask #6
Accepted
Score: 27
Test case #1
Accepted
Score: 100
Time: 8 ms
Memory: 256 KiB

Input file

2 2
aabbcc
oxoxox
dddeee
ooxxxx
1 1
1 2

Output file

3
6

Your output

3
6

System message

Exited with return code 0
Test case #2
Accepted
Score: 100
Time: 205 ms
Memory: 35688 KiB

Input file

84590 42147
aabbcb
ooxoxx
babbbc
xoxoxx
bbbabb
xoxoox
caaaca
xoxoxo
cbbaab
xxoooo
abcaac
ooxoox
acbc
<1678940 bytes omitted>

Output file

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

<84194 bytes omitted>

Your output

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

<84166 bytes omitted>

System message

Exited with return code 0
Test case #3
Accepted
Score: 100
Time: 105 ms
Memory: 35440 KiB

Input file

83386 7411
acbccb
xooxxo
aaacac
ooxoxx
babaca
ooooox
bcccab
oooxoo
aababb
xooxox
aabbbc
ooxooo
abbbc
<1254249 bytes omitted>

Output file

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

<14722 bytes omitted>

Your output

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

<14694 bytes omitted>

System message

Exited with return code 0
Test case #4
Accepted
Score: 100
Time: 367 ms
Memory: 37228 KiB

Input file

99997 100000
aaccbb
ooooox
caabac
ooxoxo
bbcbcc
oxoxoo
aabbcb
xoxooo
bbccaa
xoxoxo
bbbbcb
xxxxoo
bcc
<2578001 bytes omitted>

Output file

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

<199900 bytes omitted>

Your output

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

<199872 bytes omitted>

System message

Exited with return code 0
Test case #5
Accepted
Score: 100
Time: 354 ms
Memory: 37220 KiB

Input file

99999 99998
cacaca
oxooxo
abbcab
oxooox
ccbccc
xxooox
cbbbbb
ooxxox
cbcccc
xooxxo
bcaaca
oxooox
abac
<2578006 bytes omitted>

Output file

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4

<199896 bytes omitted>

Your output

3
4
5
4
4
3
5
5
4
3
4
4
3
4
3
3
5
5
4
3
5
3
5
5
3
4
5
4
5
4
5
3
4
4
4
5
4
5
5
4
2
4
5
3
4
4
4
5
5
4
5
2
5
4
2
4
5
5
4
3
5
4
4
4

<199868 bytes omitted>

System message

Exited with return code 0
Test case #6
Accepted
Score: 100
Time: 316 ms
Memory: 17388 KiB

Input file

36673 94424
fbefbf
xoxxox
cedcdf
xxoxox
cfcfba
xxxxxo
cbceda
xoxxoo
dadcda
oxoxox
eebaae
xxooxx
fded
<1589112 bytes omitted>

Output file

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

<188748 bytes omitted>

Your output

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

<188720 bytes omitted>

System message

Exited with return code 0
Test case #7
Accepted
Score: 100
Time: 137 ms
Memory: 17516 KiB

Input file

35469 26985
cbaeba
oxooxo
accfde
oxxooo
daebbf
oooxxo
bdddcf
xoxxoo
effaff
ooxoxx
acdfdc
oxxooo
aaba
<803588 bytes omitted>

Output file

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2

<53870 bytes omitted>

Your output

5
4
5
3
2
2
4
3
4
4
4
2
3
4
4
5
3
4
3
2
2
3
4
4
4
3
4
5
4
2
5
3
4
3
3
5
4
4
3
3
3
3
5
3
3
3
3
4
3
2
4
4
4
3
4
3
3
2
3
2
4
3
3
4

<53842 bytes omitted>

System message

Exited with return code 0
Test case #8
Accepted
Score: 100
Time: 364 ms
Memory: 36200 KiB

Input file

88751 98586
aaacde
oxoxox
dcfdfc
oxxxxx
babdba
oooooo
fcedfe
xxxxxx
acffbb
oxxxoo
fecccd
xxxxxo
dacf
<2400756 bytes omitted>

Output file

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2

<197072 bytes omitted>

Your output

2
3
4
3
1
2
3
0
3
1
2
2
2
2
3
2
3
1
3
3
4
5
2
3
3
2
3
6
4
4
4
2
2
2
3
2
1
2
4
0
2
2
3
3
2
2
5
2
4
2
3
1
3
4
2
3
1
4
3
3
2
2
2
3

<197044 bytes omitted>

System message

Exited with return code 0
Test case #9
Accepted
Score: 100
Time: 369 ms
Memory: 37228 KiB

Input file

99998 99997
fbcfcf
ooxxox
eccdde
xxxxoo
dfbcbe
ooxxoo
fffcaf
xoxxox
faacab
oxoxox
dafeaf
ooooxx
ccac
<2577652 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #10
Accepted
Score: 100
Time: 378 ms
Memory: 37228 KiB

Input file

99993 99997
fcbcea
xoooxo
edacfa
xoxoxo
bfccfd
oxooxo
cabbca
ooooxx
eacdee
xoooxx
dbcffa
oooxxo
ceae
<2577464 bytes omitted>

Output file

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

<199894 bytes omitted>

Your output

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

<199866 bytes omitted>

System message

Exited with return code 0
Test case #11
Accepted
Score: 100
Time: 61 ms
Memory: 8812 KiB

Input file

17541 11593
bbcaac
oxoxoo
ccabac
ooxooo
bcbacb
xoxooo
ccabba
oooxox
babaca
xxooox
cbacab
ooxoox
bcca
<369890 bytes omitted>

Output file

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
<24894 bytes omitted>

Your output

4
4
4
4
4
5
3
6
4
4
4
4
2
-1
5
4
5
3
2
2
2
1
-1
5
5
4
-1
4
6
5
-1
-1
5
-1
4
3
4
5
4
-1
5
-1
4
4
5
-1
5
4
3
2
-1
-1
5
3
5
3
4
5
4
<24866 bytes omitted>

System message

Exited with return code 0
Test case #12
Accepted
Score: 100
Time: 375 ms
Memory: 37376 KiB

Input file

99997 99992
baaabc
oxxxoo
cbcbab
oxxoxo
bbbbcc
xxooox
abaabb
xoxxxo
abccca
xoxoxx
bbbaaa
oxoxxx
cbab
<2577694 bytes omitted>

Output file

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

<216400 bytes omitted>

Your output

1
-1
3
3
4
3
3
2
2
-1
3
3
3
2
3
2
3
4
-1
2
2
3
3
-1
3
-1
3
3
-1
2
4
-1
3
3
-1
3
1
0
1
4
3
2
3
1
3
2
4
4
2
2
2
3
3
1
2
-1
3
3
3
3
<216372 bytes omitted>

System message

Exited with return code 0
Test case #13
Accepted
Score: 100
Time: 366 ms
Memory: 37228 KiB

Input file

99998 99993
babbcc
oxxxox
bcbabb
xooxxx
ccccab
xxoxxo
bcbbcc
xxooox
bbbbba
oxoxxx
aaacab
xxxoxo
abcc
<2577579 bytes omitted>

Output file

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
<217609 bytes omitted>

Your output

2
3
2
2
2
2
-1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
2
3
-1
2
2
3
1
2
-1
2
2
2
2
2
2
-1
3
2
2
2
2
3
2
1
-1
2
2
2
2
1
2
2
2
2
-1
2
1
2
-1
<217581 bytes omitted>

System message

Exited with return code 0
Test case #14
Accepted
Score: 100
Time: 260 ms
Memory: 34316 KiB

Input file

70828 65903
cedfca
ooxooo
abbfba
oxxoxx
fddfad
xxxoox
bcbcbb
ooxoxx
ebcdce
oxoxox
fbeeff
xxxooo
aebf
<1761814 bytes omitted>

Output file

6
1
5
5
4
3
3
4
4
4
4
3
-1
4
4
-1
4
4
6
-1
5
3
2
-1
3
1
4
-1
1
4
5
5
3
2
3
4
4
3
4
3
-1
-1
2
4
5
3
3
<140089 bytes omitted>

Your output

6
1
5
5
4
3
3
4
4
4
4
3
-1
4
4
-1
4
4
6
-1
5
3
2
-1
3
1
4
-1
1
4
5
5
3
2
3
4
4
3
4
3
-1
-1
2
4
5
3
3
2
3
1
4
1
3
-1
3
-1
4
4
3
-
<140061 bytes omitted>

System message

Exited with return code 0
Test case #15
Accepted
Score: 100
Time: 170 ms
Memory: 34192 KiB

Input file

69624 31167
cafeab
ooxoxo
afabfa
oxxoxx
baefbe
oooxxo
dfacfe
xxooxo
cfaaca
oxoxxo
cbddad
xoxxox
dabb
<1338647 bytes omitted>

Output file

3
-1
5
4
6
4
5
-1
4
3
4
5
4
3
5
4
4
2
5
3
4
-1
4
2
4
4
1
3
4
3
6
-1
3
4
5
6
2
4
6
4
4
4
-1
5
5
3
4
3
<66198 bytes omitted>

Your output

3
-1
5
4
6
4
5
-1
4
3
4
5
4
3
5
4
4
2
5
3
4
-1
4
2
4
4
1
3
4
3
6
-1
3
4
5
6
2
4
6
4
4
4
-1
5
5
3
4
3
2
4
-1
-1
5
4
4
3
2
6
3
3
-
<66170 bytes omitted>

System message

Exited with return code 0
Test case #16
Accepted
Score: 100
Time: 425 ms
Memory: 37492 KiB

Input file

99998 99999
cbeacb
oxxoox
deceaa
oxoxoo
ecaeef
xooxxo
bafafd
xoxooo
fdbbfd
xxxxoo
cccece
oxxxox
ccdc
<2577321 bytes omitted>

Output file

3
4
2
5
-1
4
5
5
4
3
4
6
3
3
2
1
6
6
-1
-1
4
3
3
2
-1
4
-1
4
4
3
6
5
6
-1
-1
6
4
5
-1
3
-1
5
-1
4
3

<212373 bytes omitted>

Your output

3
4
2
5
-1
4
5
5
4
3
4
6
3
3
2
1
6
6
-1
-1
4
3
3
2
-1
4
-1
4
4
3
6
5
6
-1
-1
6
4
5
-1
3
-1
5
-1
4
3
5
3
4
-1
4
-1
3
-1
4
3
-1
-1
<212345 bytes omitted>

System message

Exited with return code 0
Test case #17
Accepted
Score: 100
Time: 432 ms
Memory: 37480 KiB

Input file

99999 99997
cbbebc
oxxxxo
babfee
xoxxox
feabdc
xxxxoo
caaded
ooooxx
facada
xooooo
baeafd
xoxoxo
efea
<2577655 bytes omitted>

Output file

5
3
3
1
2
1
3
6
5
4
-1
3
5
3
3
3
2
3
3
2
2
3
1
-1
3
3
3
6
-1
-1
4
1
2
2
2
4
2
2
3
3
3
4
3
3
-1
-1
4

<212453 bytes omitted>

Your output

5
3
3
1
2
1
3
6
5
4
-1
3
5
3
3
3
2
3
3
2
2
3
1
-1
3
3
3
6
-1
-1
4
1
2
2
2
4
2
2
3
3
3
4
3
3
-1
-1
4
3
6
3
3
-1
6
3
-1
2
3
4
4
3

<212425 bytes omitted>

System message

Exited with return code 0
Test case #18
Accepted
Score: 100
Time: 407 ms
Memory: 37356 KiB

Input file

99994 99994
fddbbd
ooxoxo
ffbced
xxoooo
afbcfb
xoxoxo
dffffc
oxxoxo
fdeceb
ooooxo
dfccff
ooxoxx
bdab
<2577440 bytes omitted>

Output file

4
5
5
2
5
5
6
-1
4
3
2
4
2
4
3
3
4
6
3
5
4
3
2
-1
5
-1
-1
5
4
5
3
4
4
5
5
6
4
5
6
5
4
5
3
-1
5
5
4
5
<213092 bytes omitted>

Your output

4
5
5
2
5
5
6
-1
4
3
2
4
2
4
3
3
4
6
3
5
4
3
2
-1
5
-1
-1
5
4
5
3
4
4
5
5
6
4
5
6
5
4
5
3
-1
5
5
4
5
6
6
5
6
2
3
3
5
4
5
3
4
4
3
<213064 bytes omitted>

System message

Exited with return code 0
Test case #19
Accepted
Score: 100
Time: 377 ms
Memory: 37180 KiB

Input file

99999 99991
ffeafe
xxxoox
ddfccc
oxoxxo
becbbe
oxooox
cabbeb
ooxoxo
ccfabb
oxooox
bdbdbc
ooxxoo
ceba
<2577761 bytes omitted>

Output file

1
6
4
2
3
4
5
2
3
5
3
5
4
4
5
4
6
3
6
4
5
5
5
3
5
4
-1
5
3
-1
5
4
-1
6
6
3
4
5
2
-1
6
4
4
6
6
5
4
3

<213061 bytes omitted>

Your output

1
6
4
2
3
4
5
2
3
5
3
5
4
4
5
4
6
3
6
4
5
5
5
3
5
4
-1
5
3
-1
5
4
-1
6
6
3
4
5
2
-1
6
4
4
6
6
5
4
3
5
4
4
-1
5
5
2
5
4
4
3
4
6
3
<213033 bytes omitted>

System message

Exited with return code 0
Test case #20
Accepted
Score: 100
Time: 160 ms
Memory: 18284 KiB

Input file

42234 34548
baaaac
ooxxxx
abcbca
xoxoxo
acbcaa
xxoxxo
bacccc
ooxxxx
bccaba
oxxxoo
bcaaac
oxoxxx
abbc
<987843 bytes omitted>

Output file

-1
3
-1
3
3
3
3
-1
3
3
3
3
3
3
-1
3
-1
-1
3
-1
3
3
-1
3
3
3
3
3
3
-1
3
3
3
3
3
-1
3
3
-1
3
3
3
3
-1

<82054 bytes omitted>

Your output

-1
3
-1
3
3
3
3
-1
3
3
3
3
3
3
-1
3
-1
-1
3
-1
3
3
-1
3
3
3
3
3
3
-1
3
3
3
3
3
-1
3
3
-1
3
3
3
3
-1
3
3
3
-1
3
3
3
-1
3
3
-1
2
3
<82026 bytes omitted>

System message

Exited with return code 0
Test case #21
Accepted
Score: 100
Time: 116 ms
Memory: 36460 KiB

Input file

90012 9353
bbbbcc
xxxxoo
bbcbcb
xxoxox
abbaba
oxxxxo
bcbbac
xoxxoo
ccbacb
ooxoxx
babccc
xoxxoo
cccbc
<1369973 bytes omitted>

Output file

-1
4
-1
4
4
4
-1
-1
4
4
-1
-1
4
4
3
-1
4
4
4
4
-1
4
4
4
4
-1
4
4
4
-1
4
4
4
4
4
-1
-1
-1
4
-1
4
4
4

<22008 bytes omitted>

Your output

-1
4
-1
4
4
4
-1
-1
4
4
-1
-1
4
4
3
-1
4
4
4
4
-1
4
4
4
4
-1
4
4
4
-1
4
4
4
4
4
-1
-1
-1
4
-1
4
4
4
4
4
4
4
-1
4
-1
-1
-1
4
-1
4
<21980 bytes omitted>

System message

Exited with return code 0
Test case #22
Accepted
Score: 100
Time: 444 ms
Memory: 37232 KiB

Input file

99995 99992
bbbccc
xxxooo
acbcbc
ooxoxo
cbabca
oxoxoo
abcbca
oxoxoo
aaaabc
xxooxo
bbccbb
xxooxx
abca
<2577796 bytes omitted>

Output file

5
5
5
-1
-1
5
5
5
5
4
-1
-1
-1
5
5
-1
5
-1
5
5
5
-1
-1
4
5
5
5
5
-1
5
5
-1
-1
5
5
5
-1
5
5
-1
5
5
-1
<239463 bytes omitted>

Your output

5
5
5
-1
-1
5
5
5
5
4
-1
-1
-1
5
5
-1
5
-1
5
5
5
-1
-1
4
5
5
5
5
-1
5
5
-1
-1
5
5
5
-1
5
5
-1
5
5
-1
5
5
-1
5
5
5
5
-1
-1
-1
-1

<239435 bytes omitted>

System message

Exited with return code 0
Test case #23
Accepted
Score: 100
Time: 370 ms
Memory: 34664 KiB

Input file

73896 69983
caccbc
xoxoox
aabaaa
xoooxo
ccbaaa
xooooo
bacaab
xooooo
acbbac
oooxox
cbccab
xooxox
cbca
<1839239 bytes omitted>

Output file

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<139866 bytes omitted>

Your output

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<139838 bytes omitted>

System message

Exited with return code 0
Test case #24
Accepted
Score: 100
Time: 427 ms
Memory: 19652 KiB

Input file

56804 97814
aacaca
oooooo
bcaacb
xoooox
cacbcc
xooxxo
bccaac
xoxooo
acbbbc
ooxxxo
acccba
oxooxo
bcba
<1910183 bytes omitted>

Output file

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<195528 bytes omitted>

Your output

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<195500 bytes omitted>

System message

Exited with return code 0
Test case #25
Accepted
Score: 100
Time: 532 ms
Memory: 37588 KiB

Input file

99999 99994
baaabb
xxxoxx
ccbaca
ooxxoo
abcaba
xxoxxo
abcbba
oxoxxx
abcaab
xxooxx
aaaaac
xoxxxo
aaab
<2559863 bytes omitted>

Output file

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4

<199888 bytes omitted>

Your output

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4

<199860 bytes omitted>

System message

Exited with return code 0
Test case #26
Accepted
Score: 100
Time: 509 ms
Memory: 37228 KiB

Input file

99992 99995
caabba
oxxoxo
cccaab
oooxoo
bacbac
xoooxo
cbccbb
oxooox
acacab
xoxooo
cababb
oxxoxo
aaca
<2559852 bytes omitted>

Output file

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<199890 bytes omitted>

Your output

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

<199862 bytes omitted>

System message

Exited with return code 0
Test case #27
Accepted
Score: 100
Time: 121 ms
Memory: 36320 KiB

Input file

91025 9592
edefaa
ooooox
ccdcfb
xxoxox
fbeeba
oxooxo
acbacd
xxxoxo
bcedde
xxoxoo
fbdccd
oxxxxo
ccddd
<1387111 bytes omitted>

Output file

6
6
6
-1
6
6
-1
6
-1
6
6
6
6
-1
6
6
-1
-1
-1
6
6
6
6
-1
-1
6
6
-1
6
6
6
6
6
6
-1
6
6
4
-1
6
6
6
-1
6
<22717 bytes omitted>

Your output

6
6
6
-1
6
6
-1
6
-1
6
6
6
6
-1
6
6
-1
-1
-1
6
6
6
6
-1
-1
6
6
-1
6
6
6
6
6
6
-1
6
6
4
-1
6
6
6
-1
6
-1
6
6
-1
6
6
6
6
6
6
6
-1

<22689 bytes omitted>

System message

Exited with return code 0
Test case #28
Accepted
Score: 100
Time: 362 ms
Memory: 17772 KiB

Input file

38802 92909
fadfbf
oxoxxo
adebca
xooxxx
adbedb
xxxoox
cbbdfc
xxxoox
eadcba
oxoxxx
dedbce
ooxxxo
fbaf
<1605521 bytes omitted>

Output file

-1
-1
-1
5
6
6
6
-1
-1
-1
6
6
6
-1
5
-1
6
6
6
4
6
6
-1
-1
1
2
6
-1
4
6
-1
-1
-1
6
-1
6
6
4
6
6
-1
6

<220162 bytes omitted>

Your output

-1
-1
-1
5
6
6
6
-1
-1
-1
6
6
6
-1
5
-1
6
6
6
4
6
6
-1
-1
1
2
6
-1
4
6
-1
-1
-1
6
-1
6
6
4
6
6
-1
6
6
-1
3
6
2
6
-1
-1
6
6
6
-1

<220134 bytes omitted>

System message

Exited with return code 0
Test case #29
Accepted
Score: 100
Time: 453 ms
Memory: 37220 KiB

Input file

99999 99992
ffffba
xxxoxx
dfbcdf
oxxoxo
edeceb
xoooox
eaddef
oxoxoo
cbeabb
oxoxxx
ceabca
ooxxox
cbba
<2577947 bytes omitted>

Output file

-1
6
6
-1
6
6
-1
-1
-1
6
-1
6
6
6
6
6
6
4
-1
-1
-1
6
-1
-1
6
6
-1
6
6
6
6
6
4
6
6
6
-1
6
-1
6
6
-1
4
<237903 bytes omitted>

Your output

-1
6
6
-1
6
6
-1
-1
-1
6
-1
6
6
6
6
6
6
4
-1
-1
-1
6
-1
-1
6
6
-1
6
6
6
6
6
4
6
6
6
-1
6
-1
6
6
-1
4
6
-1
-1
-1
-1
-1
6
6
6
-1
3
<237875 bytes omitted>

System message

Exited with return code 0
Test case #30
Accepted
Score: 100
Time: 207 ms
Memory: 9832 KiB

Input file

26338 39260
aefadc
xooxxo
edefef
oxxoxo
dcecce
xoxooo
dffeff
xxooxo
bedaed
xoxxxx
cadbfc
oxxxoo
fdaa
<799668 bytes omitted>

Output file

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<78420 bytes omitted>

Your output

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<78392 bytes omitted>

System message

Exited with return code 0
Test case #31
Accepted
Score: 100
Time: 293 ms
Memory: 18920 KiB

Input file

52350 67092
effaad
oxooox
cddbcf
xxxooo
eeffdd
oxxoxx
abaeda
ooooxx
acfbae
oooooo
acefcc
ooooxx
cebc
<1495122 bytes omitted>

Output file

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<134084 bytes omitted>

Your output

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<134056 bytes omitted>

System message

Exited with return code 0
Test case #32
Accepted
Score: 100
Time: 509 ms
Memory: 37228 KiB

Input file

99993 99992
becdca
ooooxo
ebaebf
xoooxo
bbfefa
xoooxo
abdeea
xooxoo
deaddc
xooxoo
cdafad
oxooxo
acef
<2559531 bytes omitted>

Output file

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<199884 bytes omitted>

Your output

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<199856 bytes omitted>

System message

Exited with return code 0
Test case #33
Accepted
Score: 100
Time: 467 ms
Memory: 37204 KiB

Input file

99993 99993
ffbadd
ooxxxo
cbbacf
xxxxxo
dabbde
oxxxxo
edcded
oxxxoo
fcceda
oxxoox
bdcdcb
xoxxxx
defb
<2559890 bytes omitted>

Output file

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<199886 bytes omitted>

Your output

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

<199858 bytes omitted>

System message

Exited with return code 0
Test case #34
Accepted
Score: 100
Time: 10 ms
Memory: 252 KiB

Input file

4 4
abcdee
xxxxox
abcdee
oxxxxx
abcdee
xxxxxx
aabcde
oxxxxx
1 1
2 2
3 3
4 4

Output file

6
1
6
6

Your output

6
1
6
6

System message

Exited with return code 0
Test case #35
Accepted
Score: 100
Time: 7 ms
Memory: 376 KiB

Input file

14 7
aaaaaa
oooooo
aabbcc
ooxxxx
aaaaaa
ooooox
aabbbb
ooxxox
aabbcc
oxoxoo
bbbbcc
xoxoxo
aabbcc
oooo
<134 bytes omitted>

Output file

6
6
-1
4
-1
-1
-1

Your output

6
6
-1
4
-1
-1
-1

System message

Exited with return code 0
Test case #36
Accepted
Score: 100
Time: 9 ms
Memory: 364 KiB

Input file

8 4
aaaaaa
ooooox
bcdeaa
xxxxoo
aaabbb
oooxxx
ccddee
xxxxxx
aaaaab
ooooox
ccddee
xxxxxx
aaaaab
ooooo
<32 bytes omitted>

Output file

6
3
5
6

Your output

6
3
5
6

System message

Exited with return code 0
Test case #37
Accepted
Score: 100
Time: 9 ms
Memory: 508 KiB

Input file

2 1
abcdef
oooooo
abcdee
oooooo
1 2

Output file

-1

Your output

-1

System message

Exited with return code 0
Test case #38
Accepted
Score: 100
Time: 8 ms
Memory: 256 KiB

Input file

1 1
abcdef
xxxxxx
1 1

Output file

-1

Your output

-1

System message

Exited with return code 0
Test case #39
Accepted
Score: 100
Time: 10 ms
Memory: 376 KiB

Input file

2 1
abcdef
xxxxxx
abcdef
xxxxxx
1 2

Output file

-1

Your output

-1

System message

Exited with return code 0