QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#469110#7238. Two StringspropaneAC ✓199ms56328kbC++205.9kb2024-07-09 14:32:202024-07-09 14:32:20

Judging History

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

  • [2024-07-09 14:32:20]
  • 评测
  • 测评结果:AC
  • 用时:199ms
  • 内存:56328kb
  • [2024-07-09 14:32:20]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<array>
#include<algorithm>
using namespace std;
using LL = long long;

/*
 * From https://judge.yosupo.jp/submission/52300
 * Time Complexity: Suffix Array: O(N + Character_Set_Size) time and space //
 128 --- ASCII
 *                  LCP: O(N) time and space
 * Usage:
 *       1. Suffix Array (returns s.size() elements, NOT considering
 0-length/empty suffix)
 *             auto sa = suffix_array(s); // s is the input string with ASCII
 characters
 *             auto sa_wide_char = suffix_array(s, LIM); // LIM = max(s[i]) + 2,
 s is the string with arbitary big characters.
 *       2. LCP:
 *            auto lcp = LCP(s, suffix_array(s)); // returns s.size() elements,
 where lcp[i]=LCP(sa[i], sa[i+1])
 * Status: Tested (DMOJ: ccc03s4, SPOJ: SARRAY (100pts), Yosupo's: Suffix Array
 & Number of Substrings, CodeForces EDU
 */
// Based on: Rickypon, https://judge.yosupo.jp/submission/10105
void induced_sort(const vector<int>& vec, int val_range,
                  vector<int>& SA, const vector<bool>& sl,
                  const vector<int>& lms_idx) {
    vector<int> l(val_range, 0), r(val_range, 0);
    for (int c : vec) {
        if (c + 1 < val_range) ++l[c + 1];
        ++r[c];
    }
    partial_sum(l.begin(), l.end(), l.begin());
    partial_sum(r.begin(), r.end(), r.begin());
    fill(SA.begin(), SA.end(), -1);
    for (int i = (int)lms_idx.size() - 1; i >= 0; --i)
        SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
    for (int i : SA)
        if (i >= 1 && sl[i - 1]) SA[l[vec[i - 1]]++] = i - 1;
    fill(r.begin(), r.end(), 0);
    for (int c : vec) ++r[c];
    partial_sum(r.begin(), r.end(), r.begin());
    for (int k = (int)SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
        if (i >= 1 && !sl[i - 1]) {
            SA[--r[vec[i - 1]]] = i - 1;
        }
}

vector<int> SA_IS(const vector<int>& vec, int val_range) {
    const int n = vec.size();
    vector<int> SA(n), lms_idx;
    vector<bool> sl(n);
    sl[n - 1] = false;
    for (int i = n - 2; i >= 0; --i) {
        sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
        if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
    }
    reverse(lms_idx.begin(), lms_idx.end());
    induced_sort(vec, val_range, SA, sl, lms_idx);
    vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for (int i = 0, k = 0; i < n; ++i)
        if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
            new_lms_idx[k++] = SA[i];
        }
    int cur = 0;
    SA[n - 1] = cur;
    for (size_t k = 1; k < new_lms_idx.size(); ++k) {
        int i = new_lms_idx[k - 1], j = new_lms_idx[k];
        if (vec[i] != vec[j]) {
            SA[j] = ++cur;
            continue;
        }
        bool flag = false;
        for (int a = i + 1, b = j + 1;; ++a, ++b) {
            if (vec[a] != vec[b]) {
                flag = true;
                break;
            }
            if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
                flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
                break;
            }
        }
        SA[j] = (flag ? ++cur : cur);
    }
    for (size_t i = 0; i < lms_idx.size(); ++i) lms_vec[i] = SA[lms_idx[i]];
    if (cur + 1 < (int)lms_idx.size()) {
        auto lms_SA = SA_IS(lms_vec, cur + 1);
        for (size_t i = 0; i < lms_idx.size(); ++i) {
            new_lms_idx[i] = lms_idx[lms_SA[i]];
        }
    }
    induced_sort(vec, val_range, SA, sl, new_lms_idx);
    return SA;
}

vector<int> suffix_array(const string& s, const char first = 1,
                         const char last = 122) {
    vector<int> vec(s.size() + 1);
    copy(begin(s), end(s), begin(vec));
    for (auto& x : vec) x -= (int)first - 1;
    vec.back() = 0;
    auto ret = SA_IS(vec, (int)last - (int)first + 2);
    ret.erase(ret.begin());
    return ret;
}
// Author: https://codeforces.com/blog/entry/12796?#comment-175287
// Uses kasai's algorithm linear in time and space
pair<vector<int>, vector<int> > LCP(const string& s, const vector<int>& sa) {
    int n = s.size(), k = 0;
    vector<int> lcp(n), rank(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    for (int i = 0; i < n; i++, k ? k-- : 0) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = sa[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rank[i]] = k;
    }
    lcp[n - 1] = 0;
    return {rank, lcp};
}


int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    string s, t;
    cin >> s >> t;
    string str = s + char('a' - 1) + t + char('z' + 1);
    auto sa = suffix_array(str, 1, 127);
    auto [rk, height] = LCP(str, sa);
    
    auto get = [&](int l, int r) -> array<int, 3> {
        return {r - l + 1 - max(l, int(s.size()) - r - 1), -l, -r};
    };

    int ansl = -1, ansr = -1;

    for(int i = 0; i < sa.size(); i++){
        if (sa[i] >= s.size()) continue;
        int j = i;
        while(j + 1 < sa.size() and sa[j + 1] < s.size()) j++;
        // [i - 1, j + 1]
        vector<int> pre(height.begin() + i - 1, height.begin() + j + 1);
        auto suf = pre;
        for(int k = 1; k < pre.size(); k++) pre[k] = min(pre[k], pre[k - 1]);
        for(int k = int(suf.size()) - 2; k >= 0; k--) suf[k] = min(suf[k], suf[k + 1]);
        for(int k = i; k <= j; k++){
            int len = max(pre[k - i], suf[k - i + 1]);
            int l = sa[k], r = l + len - 1;
            // cout << l << ' ' << r << '\n';
            if (l <= r and (ansl == -1 or get(l, r) > get(ansl, ansr))){
                ansl = l, ansr = r;
            }
        }
        i = j;
    }
    cout << ansl << ' ' << ansr << '\n';

}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

riveragesmalir
toaxernaturaln

output:

4 5

result:

ok 2 number(s): "4 5"

Test #2:

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

input:

aaaaa
aaaaa

output:

0 4

result:

ok 2 number(s): "0 4"

Test #3:

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

input:

amkar
zenit

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #4:

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

input:

abacaba
cabcab

output:

3 5

result:

ok 2 number(s): "3 5"

Test #5:

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

input:

aab
bba

output:

1 1

result:

ok 2 number(s): "1 1"

Test #6:

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

input:

abcde
yeyebcbcbcbcbcbcajkdshaskjchcddasjlsjdcljcqwcbsdklhbfalsdkchfsadkjhfcbsdalcfhasldfcnlsadkcjfahsdlhasjdlvfchbasndfcalsdfjkhvsdklbacsvhdfcsdfxashdjflsbdcxsadlnfshbcsmsld

output:

1 2

result:

ok 2 number(s): "1 2"

Test #7:

score: 0
Accepted
time: 123ms
memory: 50128kb

input:

aaaaaaaabbbaabbabbaaaaaabaabbbaababaaaaaaaaaaabbbbaaaaaaaaabaabbaabbaabbbbbaaaabaabbbbabaababaababbbbabababbabbbbaabbbbaaaababbbaaaababbabbaabaabaabbababbbaaaaaabbabbabbbabaababababababaaababbbbbaaaabbaabbbaaabaabbaabbbabaaaabaaaaabbaaababbababbaababaabbbaaabaaabaabbaaaabaabbbbaabbbbabbaaabbbabbabbb...

output:

0 951423

result:

ok 2 number(s): "0 951423"

Test #8:

score: 0
Accepted
time: 124ms
memory: 56328kb

input:

bbbbaababbbbbaabbabbababbabbabababbbbbaaaabbbaaaaaabbbabbbbbaaaaababaaaababbbaabbbbbbaabababbbbbababaababbbabababbaaaaabbaabbaaaabbbaabaabbaabbbbabaabababaabbbaabbabaaaabababaabbbbbababbabbbabbaabaabbbbabbaaaabbaabbaababbabbbabbbaabbbbabaabbababaabbabaaaaaabaabababbabababbaababaabbbbaaaababbaabbbbba...

output:

0 931423

result:

ok 2 number(s): "0 931423"

Test #9:

score: 0
Accepted
time: 139ms
memory: 50376kb

input:

aababbabaaabaababaabbbbbabbbbabbaaabaabbaabbbabbaaaaababababbbababababbabaabbaababbabaaaaaabaabbbaabbabbbaabaabbabbbbbbabbaabaaaabaabaababbbbabaabaabbbaabaabbababbababaaababababbaabaabbababaababaaababbaabaabaaaabababbbbbbabaaabbaaababaaababaababbabbbaabbabbabbababbaaaabbbbbbaababbaaaaabbaabbbbaabaaa...

output:

499946 499950

result:

ok 2 number(s): "499946 499950"

Test #10:

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

input:

aacacaabcb
babcccabdbabdcddaaaccddadbaabccdabcadcccadadcbdbacccbcbadabdcdbaadacadadbdcbcbbcabcbbccbbabdaccbbdcd

output:

3 5

result:

ok 2 number(s): "3 5"

Test #11:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

49999 49999

result:

ok 2 number(s): "49999 49999"

Test #12:

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

input:

a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0 0

result:

ok 2 number(s): "0 0"

Test #13:

score: 0
Accepted
time: 43ms
memory: 17188kb

input:

baabaaabbbaaababbaabaaababababaaabaaabbbaabbbaaabaaaabbababbaaaabbbaabbbababbbabababbbbabaaabaabaaabbbbaababaabbbabbaaabaabaabbabaaaabbababaabbbbabaabaaabaaaaaabaaaabababbbbabbbabbaaaaababaabbbabbabaabbaaaaaabbababaabbabaabaaabaaaaabaababbbababaaabbabbbbbbbababbaabbbabbaabbbbbbbbbbaaabbaaaaaababbaaa...

output:

37856 299999

result:

ok 2 number(s): "37856 299999"

Test #14:

score: 0
Accepted
time: 45ms
memory: 16372kb

input:

uwhpoficehathfrqylyxoyvqraaarfmqutzndklhmhokgdbydzpkuypjflizcubqgafopoojaqtizxypcgnqqzklivajpfibxmutcxaulprkzbcjvnpwhednzcjjznlgaquuneftrxbvywudjkqfxfrtjjckeximxukcnosltzebllvizewrlhkooqtzjttrbxbgmfyssxntecbreospiljdrfjkthcatwondednpmhmrohsykjaylbhxltyquvwvcyupuqbujyoiooyedebgwpqrcbmxsraxefvhqudorhj...

output:

149999 150003

result:

ok 2 number(s): "149999 150003"

Test #15:

score: 0
Accepted
time: 35ms
memory: 17696kb

input:

bbbbbbbaabbbaabbaaaabbbbbbaaabbaaaaabbbabababaabbaabbbaabbbabaaabbbababababbabaaabaabbbaababbabaababbbbaabaabaabababbaababbbabaaaaabbaaaabaabbaabbbaaaaabaabbbbbaabaaaaaababaaabbabbabbbbabbbaaaabbbbabbbbbbaaaabbabbbbbbbabbbbbbababbabbbbabbabbabaaabbbbbaaaababbbabbbbbbbbbbbbaaababababaababaababaababaa...

output:

149998 150001

result:

ok 2 number(s): "149998 150001"

Test #16:

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

input:

baaddddaaddbbdadabddddbaaadaabcacbccddbcbbddcabadadccddcddbbabdbccbdccdabbdcbbccadabaccbabaddcbabdab
dccbdcaddbacabbdbbbddaadacdbcddcdbcdacccdbdadddcaabcbbaaabcdcdadbdcdacbccacdabccccbccdbdcacdbcbdcbda

output:

48 50

result:

ok 2 number(s): "48 50"

Test #17:

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

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

2048 2048

result:

ok 2 number(s): "2048 2048"

Test #18:

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

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

16384 16386

result:

ok 2 number(s): "16384 16386"

Test #19:

score: 0
Accepted
time: 21ms
memory: 15804kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

131072 131072

result:

ok 2 number(s): "131072 131072"

Test #20:

score: 0
Accepted
time: 19ms
memory: 13244kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

65536 65536

result:

ok 2 number(s): "65536 65536"

Test #21:

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

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

0 0

result:

ok 2 number(s): "0 0"

Test #22:

score: 0
Accepted
time: 29ms
memory: 16836kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

131072 147455

result:

ok 2 number(s): "131072 147455"

Test #23:

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

input:

babba
babbababbabba

output:

0 4

result:

ok 2 number(s): "0 4"

Test #24:

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

input:

babbababbabbababbababbabbababbabba
ba

output:

16 17

result:

ok 2 number(s): "16 17"

Test #25:

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

input:

babbababbabbababbababbabbababbabbababbababbabbababbabab
b

output:

26 26

result:

ok 2 number(s): "26 26"

Test #26:

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

input:

babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabb...

output:

0 4180

result:

ok 2 number(s): "0 4180"

Test #27:

score: 0
Accepted
time: 24ms
memory: 11156kb

input:

babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabb...

output:

0 121392

result:

ok 2 number(s): "0 121392"

Test #28:

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

input:

babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabb...

output:

92736 103681

result:

ok 2 number(s): "92736 103681"

Test #29:

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

input:

babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabb...

output:

0 75024

result:

ok 2 number(s): "0 75024"

Test #30:

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

input:

babbababbabbababbababbabbababbabbababbababbabbababbabab
babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbab...

output:

0 54

result:

ok 2 number(s): "0 54"

Test #31:

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

input:

babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabb...

output:

144 232

result:

ok 2 number(s): "144 232"

Test #32:

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

input:

iiifffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

30024 70023

result:

ok 2 number(s): "30024 70023"

Test #33:

score: 0
Accepted
time: 6ms
memory: 5744kb

input:

aaafffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3 20002

result:

ok 2 number(s): "3 20002"

Test #34:

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

input:

hhhfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

30012 60014

result:

ok 2 number(s): "30012 60014"

Test #35:

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

input:

ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

60018 110020

result:

ok 2 number(s): "60018 110020"

Test #36:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

8975 91025

result:

ok 2 number(s): "8975 91025"

Test #37:

score: 0
Accepted
time: 16ms
memory: 16196kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0 299999

result:

ok 2 number(s): "0 299999"

Test #38:

score: 0
Accepted
time: 20ms
memory: 15924kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

137737 159804

result:

ok 2 number(s): "137737 159804"

Test #39:

score: 0
Accepted
time: 17ms
memory: 15784kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

136642 186947

result:

ok 2 number(s): "136642 186947"

Test #40:

score: 0
Accepted
time: 24ms
memory: 16012kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0 299998

result:

ok 2 number(s): "0 299998"

Test #41:

score: 0
Accepted
time: 47ms
memory: 17396kb

input:

bbaababcabacbcaccaabacababcaacabcbccabbccabacbabaccacccbccacbcabacccbcbaaccabccbaabbcbaccccbaaabcbbaaccbcacbaabbacccaacabcacbabbcaccbaabbabaaabaaaacbabbabbacbccbaaacbccacbccbbaccbbaaccacbacbcbacaacbaacbaabacaccbaaccbbcbbccbacaaaaaccacbbbaaccaaabbaaccccbaccbccbbaacacbaaccbaaccbbaacabacbacbabccbcbacba...

output:

149995 150004

result:

ok 2 number(s): "149995 150004"

Test #42:

score: 0
Accepted
time: 41ms
memory: 17552kb

input:

aaaaaabbbaabbbaaaaabaaaabbbbabbabaabbababaaaaaaabbaabbbbabbaaaababaababbabbbababaabaabaabbbaaabababaaaaabaaaaaabbaaabaaaaabbabaaaabbbaababbbaaaaabaaabbaaabbaabbbbababbaaaababababbababbbabbaaabbababbbbbabaababbabbabbbaabbaabaaababaabbbbaabbbbabbbabbaaabaabaaaaaaabaababbbbbabbabbbbaaaabbaaaabaabaaaaab...

output:

149993 150006

result:

ok 2 number(s): "149993 150006"

Test #43:

score: 0
Accepted
time: 45ms
memory: 17428kb

input:

ddbcbaaccbcaadcccacddaaadcccaddbbcdccccbcdbddadbbcbdcdcbdddbbcdcbdacacabdcacdadbbcdddaddbbdaacdaccacdaaababbaccacabdbddadccdabcbdddcdaadaacbdbbdbabddaccdbbcbcadcdbcbdcdaccaddcdadbadaadacccdbbadacdddadbcbdddddbdaaabcbcbdbdcbcaacddcbdaaddbcdddccbcbcdbccbdbaacbcaadbcaaadaccdcddbcdcbbcbbbddcbbabbcadadbd...

output:

149998 150002

result:

ok 2 number(s): "149998 150002"

Test #44:

score: 0
Accepted
time: 48ms
memory: 17512kb

input:

dbadbadcbdbbddabdabdababcdbcbdcadcbbadaaabacccadbacadbcbaadcbaaddcaccddbaacccaabdcabccdaccbcbcaddccdcbccbcdccdcccccccaddbcbcccacabddcaddcadcaacccdcdcabcbaabaabacbdacbcdabbbbcbdccbddccabdbacdccbdbaaaaaddbdacddddccbcbccabdaabaacbdcabdcdbcdaacabccddddadabacdbddbcacaccadadddbcabacbaacdbdaddcabdbdbcbcddb...

output:

149997 150000

result:

ok 2 number(s): "149997 150000"

Test #45:

score: 0
Accepted
time: 45ms
memory: 17608kb

input:

aaabaaaaaabaabbbbbbbbbabaabbbbabaabbbbbabababbbabbbbbbbbaaabaabaaaaabbbabbabbbbbabaabaabaabababbbbabaaaabaaaabbbbabbabaaaaaaaaabbabbbabbabaabaabbbbbbbababbbbabbababaabaabbababbabbbbabaaabaaabbbbabbabaabbabaabbabaaabaabaaabbaababaabababbaaaabbaabbaabbabababbbbabbaaabaaaaaaaabbbbbabbaaaaaababaaabaaabb...

output:

149996 150004

result:

ok 2 number(s): "149996 150004"

Test #46:

score: 0
Accepted
time: 42ms
memory: 17156kb

input:

bbbaaabaabbbabbbababababbbaabbbabaababbbaabbabbbbababbabbbbbbaaabbaaabaabbabbabaaabbbaaaabbbbbabaaaabbababbbaaabaabaabbbaaabbabbbaaaaabbabababbbabbabbaabaaaaaabaaaabbbbbaabaabaabaabaaabaabbaaaabbbbbbaaaaaabbbbbbbabaaabaaabababbababaaaabbabbaabbbbaabbbaabbbabbabbbaabbaabababbbbabaabaabbaababaababaaba...

output:

37856 299999

result:

ok 2 number(s): "37856 299999"

Test #47:

score: 0
Accepted
time: 43ms
memory: 18700kb

input:

abbbbbabaaababbbbaaaabbbbaabbbaaabaababaaabababbababbbbaaaabbbaabbbbbbbaaabbabbaabbabaaabbbabaaaababaababbaaabbbaabababbbabaabbbbaaaaaabaabbaababbbbaababaaabbbabbabaaaabbaaababaabbbbbabababbaabaabaaaabbbbbbaabbabaaaaabbbbaaaabbbabbbbbbaabbababbaaababbbbaaaaaaababababaaababbabababbbaaabababaabaaaabab...

output:

27856 289999

result:

ok 2 number(s): "27856 289999"

Test #48:

score: 0
Accepted
time: 43ms
memory: 17532kb

input:

aababbabbbabbabaaaaaabaababaabaaaaabbbbbaabbbbbbabaaabababbaabaaaababbabbbbaaaaabbbaabbababbbaabababbbabaaabbbbababaababaaaabbbbaababbbbaaabaaaaabbabbababbaabbabbbbabbbabbbbbbbbbbbabaababbbaabbbaaabbbbbbbbbabaabbbaabaabaabaaabaabababbabaabbbabaaabbbabbbbbbabbbaabbaabbaabababbababaaaaabaababbbbabaaab...

output:

37855 299998

result:

ok 2 number(s): "37855 299998"

Test #49:

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

input:

aaa
baa

output:

0 1

result:

ok 2 number(s): "0 1"

Test #50:

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

input:

aaa
aab

output:

0 1

result:

ok 2 number(s): "0 1"

Test #51:

score: 0
Accepted
time: 55ms
memory: 44392kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

43843 956155

result:

ok 2 number(s): "43843 956155"

Test #52:

score: 0
Accepted
time: 39ms
memory: 27044kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

449995 549994

result:

ok 2 number(s): "449995 549994"

Test #53:

score: 0
Accepted
time: 134ms
memory: 37584kb

input:

ojsxwxvgzjgafejcecruyjcjijkxloguufynkzhroahnofzxsdkijdtprlroqkheycawwtuapcfoeojpwchipgdymwpslpkcqkwccmtusxkvsjaeqenklxmlolhldksgdudccndxmauplbthtubkgjgtycwoueqkufncbalmsaslqrmxhtqsbxdiexfxltvktycqwitqnbmwhqwimnzgdctzpqxgskowxgausuthcehozqabkekydsnjafxgawnwxdxkcmmgpqeoxejfjfjgxnrxwvfshjdjuosmmiuqvjhx...

output:

399998 400002

result:

ok 2 number(s): "399998 400002"

Test #54:

score: 0
Accepted
time: 106ms
memory: 36084kb

input:

cacaacdcacdadccdaadcddaabbbbbcabddcdbdacbbddaaabbbddbaabacbdddbaacddbadbaadadbdbbcbcdabbddcdabcbabbbabcbddbdcdddadaadbdccaabadaadabcccdaaddaabaddaaadcdcdcdbacabbdbbddbbbcddbacbacbbcadaddadcabacddcdaaabcabbcbcbddbabbadbbaacdccdcbdcababcaaacabbddbddcbdacbbcbccccbdcacbbccddbaddabadcdaadbdcdacdbdbababcc...

output:

207561 600499

result:

ok 2 number(s): "207561 600499"

Test #55:

score: 0
Accepted
time: 37ms
memory: 23296kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

131072 131072

result:

ok 2 number(s): "131072 131072"

Test #56:

score: 0
Accepted
time: 48ms
memory: 27832kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

262144 262146

result:

ok 2 number(s): "262144 262146"

Test #57:

score: 0
Accepted
time: 34ms
memory: 22764kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

262144 262144

result:

ok 2 number(s): "262144 262144"

Test #58:

score: 0
Accepted
time: 55ms
memory: 28284kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

262144 262144

result:

ok 2 number(s): "262144 262144"

Test #59:

score: 0
Accepted
time: 33ms
memory: 20528kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

0 0

result:

ok 2 number(s): "0 0"

Test #60:

score: 0
Accepted
time: 38ms
memory: 22244kb

input:

abbcbccdbccdcddebccdcddecddedeefbccdcddecddedeefcddedeefdeefeffgbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghbccdcddecddedeefcddedeefdeefeffgcddedeefdeefeffgdeefeffgeffgfgghcddedeefdeefeffgdeefeffgeffgfgghdeefeffgeffgfggheffgfgghfgghghhibccdcddecddedeefcddedeefdeefeffgcddedeefdeef...

output:

262144 278527

result:

ok 2 number(s): "262144 278527"

Test #61:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0 999994

result:

ok 2 number(s): "0 999994"

Test #62:

score: 0
Accepted
time: 68ms
memory: 47136kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

71963 999997

result:

ok 2 number(s): "71963 999997"

Test #63:

score: 0
Accepted
time: 45ms
memory: 32440kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

336526 663470

result:

ok 2 number(s): "336526 663470"

Test #64:

score: 0
Accepted
time: 65ms
memory: 45360kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

85732 999997

result:

ok 2 number(s): "85732 999997"

Test #65:

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

input:

db
bbababbabaab

output:

1 1

result:

ok 2 number(s): "1 1"

Test #66:

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

input:

acbcbcccbbabbbababaa
bcbcb

output:

7 8

result:

ok 2 number(s): "7 8"

Test #67:

score: 0
Accepted
time: 65ms
memory: 46404kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #68:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

499998 500000

result:

ok 2 number(s): "499998 500000"

Test #69:

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

input:

notfromthe
mineeyehat

output:

6 6

result:

ok 2 number(s): "6 6"

Test #70:

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

input:

cupidlaidby
farewellthouarttoodearformypossessingandlikeenoughthouknowstthyestimatethecharterofthyworthgivesthee

output:

4 5

result:

ok 2 number(s): "4 5"

Test #71:

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

input:

farewellthouarttoodearformypossessingandlikeenoughthouknowstthyestimatethecharterofthyworthgivestheereleasingmybondsintheearealldeterminateforhowdoiholdtheebutbythygrantingandforthatricheswhereismydeservingthecauseofthisfairgiftinmeiswantingandsomypatentbackagainisswervingthyselfthougavstthyownworth...

output:

5323 7265

result:

ok 2 number(s): "5323 7265"

Test #72:

score: 0
Accepted
time: 126ms
memory: 50616kb

input:

mineeyehathplayedthepainterandhathstelledthybeautysformintableofmyheartmybodyistheframewhereintisheldandperspectiveitisbestpaintersartforthroughthepaintermustyouseehisskilltofindwhereyourtrueimagepicturedlieswhichinmybosomsshopishangingstillthathathhiswindowsglazedwiththineeyesnowseewhatgoodturnseye...

output:

498964 501298

result:

ok 2 number(s): "498964 501298"

Test #73:

score: 0
Accepted
time: 115ms
memory: 48668kb

input:

cupidlaidbyhisbrandandfellasleepamaidofdiansthisadvantagefoundandhislovekindlingfiredidquicklysteepinacoldvalleyfountainofthatgroundwhichborrowedfromthisholyfireofloveadatelesslivelyheatstilltoendureandgrewaseetingbathwhichyetmenproveagainststrangemaladiesasovereigncurebutatmymistresseyelovesbrandne...

output:

447882 450776

result:

ok 2 number(s): "447882 450776"

Test #74:

score: 0
Accepted
time: 115ms
memory: 48176kb

input:

notfromthestarsdoimyjudgementpluckandyetmethinksihaveastronomybutnottotellofgoodorevilluckofplaguesofdearthsorseasonsqualitynorcanifortunetobriefminutestellpointingtoeachhisthunderrainandwindorsaywithprincesifitshallgowellbyoftpredictthatiinheavenfindbutfromthineeyesmyknowledgeideriveandconstantstar...

output:

498907 502308

result:

ok 2 number(s): "498907 502308"

Test #75:

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

input:

gffifgfkgi
vxppnqypxw

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #76:

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

input:

kefgmmekcbbelkjclbackmadjjgaieiiekkgbbgibbjechihlegbkachdigmjhfmebihmcflfmejjabkbjggclihbhdcafmigegd
xvsqnoznznroqwsotprvtsqrzvxtxtuxvvyvsvunpqwuxqwynutzozwrzpqvyozwqroptzrupuwxwrnusqnvounruonppsywqrztvsyuryqzpzpwuwrptwpxvnwqpqqqznsrzvppvywzpxpqxtpzzqsnsxunyvtoqwqvvunqqxuurqptnzxsoyrnwzoosvprrpwtvzs...

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #77:

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

input:

ebccgjmaeegfhldmemfdiilghfgkgikaejghagkhhkgajjimfdhfbeiibckielbbjlgjgghjiffmcmhbckabhjdfhddjbecmaccblhkfamcjkkfgflgbglfiahaicbeedejfjgdbegmjjgblfebfafajklbdggcjidahiffldfmccabcdkfgdgmmbbcgkimjgcjjaaddaaejmbbgegfcggfdmjkadfalkkjcgjkihccaeelegefcljkgcgmedgajkedgkehlkjggeaakjfgmbkffdlaaielkeaglgfilkkef...

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #78:

score: 0
Accepted
time: 67ms
memory: 27908kb

input:

ijdfkbeeejmbggcdlddbibedeffjahaciilfdkgikjccchdlbcfmeggfgfkackgbdgkmfmfdlallfifagmlmcifaghhgfbfhfbjeackaakcljhccaeecamkbklkjagggahjmegifmacjjajfimmmmlgmmdhhfhifgeklbilcgiidheeabcfdjhfdfhgmckelelgjgmkhafhbgliakmmammbgdbhlhjimielbhgledbfllajmbddedceacfjkmlejehlhlhckjbdfcfkafkigcacbfkelihahicgabaaghdhm...

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #79:

score: 0
Accepted
time: 133ms
memory: 39292kb

input:

gelmkblggajkjabdhlbikggjmfblcflahbldhmbfkligfaefklidagbameacigiiakjimfhggdgkjdgdejigifehliaeahcjhkikmilmbcedcmmaagkiimjjiegfbeilbkhgghkceciadddlfealefelhljbfbjibhlcgbfabfcelhcmjcfhmemafbjcehcciidbccifdgkbfddchdfdjffchidljmmabjalcgldeelffifledbmembjakeljcdkjfddlahhgldlekebbcmafaebajigelcbfkdjckijfgll...

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #80:

score: 0
Accepted
time: 146ms
memory: 46476kb

input:

acefdeimkjfellaicjbeejfebkffacghddaahhegdjebifbjggfhgceaaklddhkeghgcmjhjmkklmmllcjcfkbkbaeajflcmmmadcaclajihefjdlcihadgfjjhjimgblihadldckmebhlcfifagmilhdjigclkgaklkhaimgcdldjhiljhbcclcdkaeffkibgcmlkkldeajllkhkfecajgddkfbkbichiigmedcdiddgejkjldadjelmehbddggkmejhagkkbheabjcflfafmfihkgigbdgdlaimmmmbimm...

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #81:

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

input:

a
a

output:

0 0

result:

ok 2 number(s): "0 0"

Test #82:

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

input:

a
b

output:

-1 -1

result:

ok 2 number(s): "-1 -1"

Test #83:

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

input:

ab
ba

output:

0 0

result:

ok 2 number(s): "0 0"

Test #84:

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

input:

ab
bb

output:

1 1

result:

ok 2 number(s): "1 1"

Test #85:

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

input:

abc
acb

output:

1 1

result:

ok 2 number(s): "1 1"

Test #86:

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

input:

add
kljkljfgldfjhlabhjklahvbkljnhljdkhjkl

output:

1 1

result:

ok 2 number(s): "1 1"

Test #87:

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

input:

badddbb
baa

output:

0 1

result:

ok 2 number(s): "0 1"

Test #88:

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

input:

cabbaca
cabeeaca

output:

0 2

result:

ok 2 number(s): "0 2"

Test #89:

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

input:

cabeebac
cabjbac

output:

0 2

result:

ok 2 number(s): "0 2"

Test #90:

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

input:

hjguekbqldtyxnokmmdezouobstrlqbxxxkowzcqmsjltzajtvbrmtproetemtkrlwtaukfliwlbfevotysmacfihkceygzrxkpu
qtnexzlkzurweqyzwpbqrtyxnokmmdezouobstrlqbxxxkowzcqmsjltzajtvbrmtproetegcryfkeoirqhdeqcgoukvidmgnruegaskadbdhcpfjndgqkvp

output:

10 59

result:

ok 2 number(s): "10 59"

Test #91:

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

input:

hhplcuqynafzwvyfszzqnvfaizxlsqcnrqjejxxptclfhusbmqlomfgrjdpfvzmyohnqjnmqqdxxvajefsnwsjfkmaswdtorzpod
keajiwbggbhropcygulkcbdnpqfywadjtgmlkbdmyerysgwgchujxvpucntiwoqpgomhaqkcnhbnizxlsqcnrqjejxxptclfhusbmqlomfgrjdpfvzmyohnqjnmqqdlfyjrmcbrgbndokkyuzekgcyayosxobupfdtovqbmduqlwfvtnrxwxqzyihmxoxkbhaacjoodt

output:

24 73

result:

ok 2 number(s): "24 73"

Test #92:

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

input:

qihcowxvfnqosvszwoaibobgjhngwclhzvzzqvfbxnsywdyqkmspzzjkghscpjakagirxvtyvdgqqdemcfwoakdhjboojsojwrpcyloupduhxmyagzymcbsurxnnvtlstijdvkhooidowpsfdivlgrcmzmwmiutmtjwhnqziqylwjxhokbvhjlcjzcntoxkjjkjzmzoyqogycgfbiimwfqmultavrheieocglbidozxffhzsrpeopmxnrlkltudpopmfbcyvxtieocfnyiwwihtyygrbpyugowcdmcaucval...

output:

294 793

result:

ok 2 number(s): "294 793"

Test #93:

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

input:

wxsxcyzjumjcnbfbnvejhxxaowlgagqcrhllzqhrmenubuexgvmqmqcckbqikjdqltrpswnzhfouehtcxngdjmtpolwjdkgqedhmgtkuyeyzscxhhnbiyfwjaakannfxbsuemogfmmgnxtazhhipwdmjlotxpjypdnmlkajcawhykozajsaukivjupxgtxqrbhbvbuveuirlqiyotjbzttzkkryokcptxlanfqpdbokaiaycbeueblbvjztdhiobkhhlomibojzewctepudalatwiqadwbjzlblcsffdzmsg...

output:

393 892

result:

ok 2 number(s): "393 892"

Test #94:

score: 0
Accepted
time: 2ms
memory: 4396kb

input:

kagodasswahdcmfdzekpgbzsxsnkcktqpxqwgchawkatxgywlvbnruygdxkzccwfmszxsmxaubrnmuetvmatesahqwezvlrglskhsvtgawehzprsekjvjyzhdqeshjjbeoiezajympqdofaoaswdlyczclodmkbrxdmphgvqzsqvrrvxduovzppxqlmvqwwutmvijgcgvkqtitkxrrslweafchejnufxbcnajsgwcbupdbqguzfmcxlzotrkcyiaecndjoudlajotsfztqzjkzaloxctjwlgrazlaxzvyrfc...

output:

4482 9481

result:

ok 2 number(s): "4482 9481"

Test #95:

score: 0
Accepted
time: 2ms
memory: 4100kb

input:

zlkdkethdpoesnvqwyojsfdscmnpkbsvkyuzmpcwuhzdyeqkvqadojfyjutjogqfbryhxhoarjocsuchgdwafpysfmlpkxwtvjeawuhrkyobjdcbtvrffctktzjkzfildzxytelbtlvooymlbqysdidatmfxfyyxhndhaxrmdqdqvsgsdtbvdeazlgcujezqtitrxjbbbptezsvtnunhwxlwvwwszrslxejqhkvxaaxagnjlyxbkbmtbgobydxewkjjjhbwcdvfrvdkretrasvydpqtdchwfklbktlcvfhhp...

output:

1508 6507

result:

ok 2 number(s): "1508 6507"

Test #96:

score: 0
Accepted
time: 2ms
memory: 4100kb

input:

zgfgduwzizbxnkouixxdbggbmxvkjfnhjqhphbddorslnuevmaognncjbrvlrpjefmedyjqzthwmoscxfoninmkxeayigrvhwiilzecgggajaztdutadbwlvwgcsjemjyfencigaocarurkyysdsnwxubunxngmebygawmpttkebyoirgbbpdnehdffkozkucuhjojanvdhufobpvgcxihasumgasbvokzzzadyduldurdnotoaigqrigzuzgstqqyyupokxiutpoedymdabirprpdilbodvnyghkwvqeifb...

output:

2453 7452

result:

ok 2 number(s): "2453 7452"

Test #97:

score: 0
Accepted
time: 185ms
memory: 51880kb

input:

fkpwoackadwsxopxbwfixmqyykfrfepscysxsnwtbcqtixbgalhwzpuiitvvddllyfrafjrumtfijmhpmehcekioiqjecuszuusfsscxkkcksvyebsnysbjrrahmiodgrscyrdtkybzblmplahrfixmsrftmvwwsnfwugauzkgbfzckwpggajeresyxdvsymnlqahnbklvbmcjtensjoshhqowzytlnugssjuolmbilcncxpchwhcxaylaxscqvbyuoxtldlaoxlbuqwfhutullgteiokefqbyntcsfsgntw...

output:

4969 504968

result:

ok 2 number(s): "4969 504968"

Test #98:

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

input:

ahtudtkohzhwnndmazfbtecybbjffmncrxszbhtzzwcjokgtsnumqabaudvbzegvuzzjgadaodywzqbwojrwbbmnhllpnhynjkfzytmlokgvbzumwgovvzsbcstpbxgckhfitabzqxfbhsfzuofgmkylawvadjwnurcbgkizdofzjtvoclepbxcrzecgszpdikbojcjhkimjsadholcqzkfpaydyuixxvqebloanrwzpusbjmkpbjkgnucbbqpqmdlgncwydsgxxlqvqbdpatiujusjjvjnlstnvlemmkecu...

output:

10128 510127

result:

ok 2 number(s): "10128 510127"

Test #99:

score: 0
Accepted
time: 191ms
memory: 51608kb

input:

tpcormmrwvcacrgfqmfuvlojrlvaqqfqkspjlghhxbwuehfjmvmolidgorkhwdknlnfucnihgbyfmlsbguypyrgrecmidakhmasckwjuvsjklblhcsdbaqragqcxjdzwjdnmkgtollafrkzbppjydselocfbnsptlvzcjnxgemppvjqozflrftttviqbwwtrckiuwjkdizzldnaxmbuyrkexzcbtsbekgbxwpjbpzutrmpkjwlrroxfsauujalerunssflrppnrvuscjbjsjhihvogckauytyexsmofvteqt...

output:

20012 520011

result:

ok 2 number(s): "20012 520011"

Test #100:

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

input:

rpxqfpovtcssqybsytvzvxnkrqckeytxnmtlumkqqvcefhabgttefcrkyjfaauevtqurfuvosfmsuufvcwtkdyzqugmsoaeabkpidmqznhqekpdwxijyypaxkywubwdxjbbibrcpjwkxerhmlyyqwsurcfdugxlsanffoduvyppbvqhpbjfoxbowkeoglshvkvhuuxhjlnjpbsgfrcnifyeflxnhqjokmszcopkjjjonjjfqgespbptyuqcjutpiypostjjedgiyhswyghsgxbpyngozzmushorgxzyawmgd...

output:

39989 539988

result:

ok 2 number(s): "39989 539988"

Test #101:

score: 0
Accepted
time: 181ms
memory: 51832kb

input:

kfebpkjcbaoodhavgmmucmhjkvdronsvmlanxpkzyvdneaqkpyluqqdoylxznosezryehfglosombyiruzfsjagnxpxtoualspvoqueadrdpibmsudaxpleazxkbsuwcoiywipdagwyrveczqlxxidnkuujgomzsisqzbqcxquxorpoxsitqmiqnehagccanyzkqdsosynwzxovptcpgzruhxfaebnruoionriigxdpvtohygrsborryczdcxuscfkpanaxrvdwqhfuvywgxlarnkqoeesdypiqwjtzgjgnt...

output:

80103 580102

result:

ok 2 number(s): "80103 580102"

Test #102:

score: 0
Accepted
time: 199ms
memory: 51760kb

input:

hfidnevjlimahixrbfwiojukciehuzsgvdbifniyxiutyvztqrsldgeyrejuefshrxooqnunwnxetzhkhjmpawwpwtnbjlkrczyaoiqoewtcppxjcvdxzyequhbrdlmfikpzoyvnpffffifxmbpmljivjwwwzpxrpxgxgchfzzomfxgmnfopfjghowgihybfzntajkkbpzdrxzizfsmboqdyvebsohgplorwouzxibunxdtnfwkvcmcrhavfbviomaviklgiziihdlvplnngbyxiadqilwyawtttslcvichk...

output:

159935 659934

result:

ok 2 number(s): "159935 659934"

Test #103:

score: 0
Accepted
time: 193ms
memory: 50276kb

input:

vwgilzrtbmamqqiwligqvwobeybnonpzcavjefsqwzfkxdpjobzhoscndsbvbcapilicgvnybeacwcgfbyopsljvdljyqqtimaziwodsvjtqvpqzhvpnzujptqupnxhoijlevsomifkokqtzlupbmjslhrkphromlatfimmorszoposnaceawbxurcgvgamlrnnhuhtwzwgzpqijcofsmghdqhstjvsggfwimqdquizolybxvorwcesaoytqyiicfxptynvnuvzqqslsytbmqvtdwqfarfwqfplyoyliprbb...

output:

319396 819395

result:

ok 2 number(s): "319396 819395"