QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191621#2704. Lexicographical Lecturingbeshoyhany#AC ✓873ms54420kbC++173.5kb2023-09-30 03:17:462023-09-30 03:17:46

Judging History

This is the latest submission verdict.

  • [2023-09-30 03:17:46]
  • Judged
  • Verdict: AC
  • Time: 873ms
  • Memory: 54420kb
  • [2023-09-30 03:17:46]
  • Submitted

answer

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("Ofast,no-stack-protector", "omit-frame-pointer", "inline", "-ffast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,fma,popcnt,abm,mmx,avx")

#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 2e4 + 5, LOG = 25;

ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
    return (a * b) / __gcd(a, b);
}

int mul(int a, int b) {
    ll ret = 1ll * a * b;
    if(ret >= MOD)ret %= MOD;
    return ret;
}

int add(int a, int b) {
    if(a < 0)a += MOD;
    if(b < 0)b += MOD;
    a += b;
    if(a >= MOD)a -= MOD;
    return a;
}

int pw(int x, int y) {
    int ret = 1;
    while (y > 0) {
        if (y % 2 == 0) {
            x = mul(x, x);
            y = y / 2;
        } else {
            ret = mul(ret, x);
            y = y - 1;
        }
    }
    return ret;
}

const int P1 = 31, P2 = 37;

int pw1[N], pw2[N], inv1[N], inv2[N];

void pre() {
    pw1[0] = inv1[0] = pw2[0] = inv2[0] = 1;
    int mulInv1 = pw(P1, MOD - 2);
    int mulInv2 = pw(P2, MOD - 2);
    for (int i = 1; i < N; i++) {
        pw1[i] = mul(pw1[i - 1], P1);
        pw2[i] = mul(pw2[i - 1], P2);
        inv1[i] = mul(inv1[i - 1], mulInv1);
        inv2[i] = mul(inv2[i - 1], mulInv2);
    }
}

struct Hash {
    vector<int> prefixHash;

    Hash() {

    }

    Hash(string &s) {
        prefixHash = vector<int>(s.size(), 0);
        for (int i = 0; i < s.size(); i++) {
            prefixHash[i] = mul(s[i] - 'a' + 1, pw1[i]);
            if (i)
                prefixHash[i] = add(prefixHash[i], prefixHash[i - 1]);
        }
    }

    int getRangeHashVal(int l, int r) {
        return mul(add(prefixHash[r], -(l ? prefixHash[l - 1] : 0)), inv1[l]);

    }
};


void solve() {
    int n, l;
    cin >> n >> l;
    vector<Hash> vec(n);
    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];

    }
    sort(all(s));
    for (int i = 0; i < n; ++i) {
        vec[i] = Hash(s[i]);
    }

    int a = 0, b = l - 1;
    for (int i = 0; i < l; ++i) {

        int mx = i;
        for (int j = 1; j < n; ++j) {
            int st = i, en = l - 1, ind = -1;
            while (st <= en){
                int mid = (st + en) / 2;
                if(vec[j].getRangeHashVal(i, mid) != vec[j - 1].getRangeHashVal(i, mid)){
                    ind = mid;
                    en = mid - 1;
                }
                else{
                    st = mid + 1;
                }
            }
            if(!~ind || s[j][ind] < s[j - 1][ind]){
                mx = 1e9;
                break;
            }
            mx = max(mx, ind);
        }
        if((mx - i + 1) < (b - a + 1)){
            a = i, b = mx;
        }
    }
    cout << a + 1 << ' ' << b + 1;
}

signed main() {
    Drakon();
    pre();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3936kb

input:

2 1
a
b

output:

1 1

result:

ok 

Test #2:

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

input:

26 1
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z

output:

1 1

result:

ok 

Test #3:

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

input:

4 2
aa
ab
ba
bb

output:

1 2

result:

ok 

Test #4:

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

input:

25 2
aa
ab
ac
ad
ae
ba
bb
bc
bd
be
ca
cb
cc
cd
ce
da
db
dc
dd
de
ea
eb
ec
ed
ee

output:

1 2

result:

ok 

Test #5:

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

input:

484 2
aa
ab
ac
ad
ae
af
ag
ah
ai
aj
ak
al
am
an
ao
ap
aq
ar
as
at
au
av
ba
bb
bc
bd
be
bf
bg
bh
bi
bj
bk
bl
bm
bn
bo
bp
bq
br
bs
bt
bu
bv
ca
cb
cc
cd
ce
cf
cg
ch
ci
cj
ck
cl
cm
cn
co
cp
cq
cr
cs
ct
cu
cv
da
db
dc
dd
de
df
dg
dh
di
dj
dk
dl
dm
dn
do
dp
dq
dr
ds
dt
du
dv
ea
eb
ec
ed
ee
ef
eg
eh
ei
ej
...

output:

1 2

result:

ok 

Test #6:

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

input:

243 5
aaaaa
aaaab
aaaac
aaaba
aaabb
aaabc
aaaca
aaacb
aaacc
aabaa
aabab
aabac
aabba
aabbb
aabbc
aabca
aabcb
aabcc
aacaa
aacab
aacac
aacba
aacbb
aacbc
aacca
aaccb
aaccc
abaaa
abaab
abaac
ababa
ababb
ababc
abaca
abacb
abacc
abbaa
abbab
abbac
abbba
abbbb
abbbc
abbca
abbcb
abbcc
abcaa
abcab
abcac
abcba
...

output:

1 5

result:

ok 

Test #7:

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

input:

256 8
aaaaaaaa
aaaaaaab
aaaaaaba
aaaaaabb
aaaaabaa
aaaaabab
aaaaabba
aaaaabbb
aaaabaaa
aaaabaab
aaaababa
aaaababb
aaaabbaa
aaaabbab
aaaabbba
aaaabbbb
aaabaaaa
aaabaaab
aaabaaba
aaabaabb
aaababaa
aaababab
aaababba
aaababbb
aaabbaaa
aaabbaab
aaabbaba
aaabbabb
aaabbbaa
aaabbbab
aaabbbba
aaabbbbb
aabaaa...

output:

1 8

result:

ok 

Test #8:

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

input:

10 10
azzzzzzzzz
bzzzzzzzzz
czzzzzzzzz
dzzzzzzzzz
ezzzzzzzzz
zzzzzzzzza
zzzzzzzzzb
zzzzzzzzzc
zzzzzzzzzd
zzzzzzzzze

output:

1 10

result:

ok 

Test #9:

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

input:

10 10
aababcbaca
abacabbbac
abacabcaaa
baccbaaabb
cbabbaacbb
cbbaccaaca
cbbbaaabcb
cbbccaacaa
cbcbbbccaa
ccbcbcccaa

output:

1 7

result:

ok 

Test #10:

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

input:

10 10
aaaacaaacc
aacbacabac
bacbccacbb
bbabccbbcb
bbbbaacaac
bbcbbacbac
bccaabccaa
cbccacccac
ccaacbccbc
ccbabacccb

output:

1 3

result:

ok 

Test #11:

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

input:

4 6
aaaaaa
aaabbb
aaacaa
aaacac

output:

4 6

result:

ok 

Test #12:

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

input:

10 10
aacbaacaac
abacabaabb
acbaabcabc
acbcacabac
bcbbbaabbb
caaababcba
cbaabbacbb
cbbbcbacbc
cbcacbcccb
cbcccccccc

output:

5 7

result:

ok 

Test #13:

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

input:

10 10
bccfawjqtl
dbivwehcyz
fvtdkthxop
gajsvnggsq
jumwfltycp
oafdzbgdpz
pnbtdsvaml
uksdrbpzih
xqqjewbwoo
xsaxwciyvr

output:

1 2

result:

ok 

Test #14:

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

input:

10 10
bdqpbbsyed
cfxhfklmhh
etkqikpolw
hmqrikxang
lmicjowuoo
okczjrgaou
tbvpkkmeow
uslalygxpx
wubhnycnsm
wyqhxznavk

output:

1 2

result:

ok 

Test #15:

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

input:

10 10
ckzcqbbdqa
kizgvdefsw
scshoejhgg
tggibhkohf
uqiookmtcs
vmcrplrutp
vvuuupsvmy
wjouyqtwmt
wkxxdrvygk
wwkzszzyie

output:

6 6

result:

ok 

Test #16:

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

input:

100 100
aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid
abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd
adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...

output:

1 4

result:

ok 

Test #17:

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

input:

100 100
aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec
aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha
abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...

output:

1 4

result:

ok 

Test #18:

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

input:

100 100
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abababababababababababababababababababababababababababababababababababababababababababababababababab
acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...

output:

1 2

result:

ok 

Test #19:

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

input:

100 100
aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 100

result:

ok 

Test #20:

score: 0
Accepted
time: 36ms
memory: 28972kb

input:

500 10000
aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...

output:

1 11

result:

ok 

Test #21:

score: 0
Accepted
time: 32ms
memory: 28904kb

input:

500 10000
aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...

output:

1013 1022

result:

ok 

Test #22:

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

input:

3 5
cccca
ccgda
ccgia

output:

4 4

result:

ok 

Test #23:

score: 0
Accepted
time: 32ms
memory: 29004kb

input:

500 10000
aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...

output:

1317 1326

result:

ok 

Test #24:

score: 0
Accepted
time: 109ms
memory: 28884kb

input:

500 10000
aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...

output:

76 81

result:

ok 

Test #25:

score: 0
Accepted
time: 23ms
memory: 28912kb

input:

500 10000
acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...

output:

1 4

result:

ok 

Test #26:

score: 0
Accepted
time: 18ms
memory: 28964kb

input:

500 10000
aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...

output:

1 4

result:

ok 

Test #27:

score: 0
Accepted
time: 30ms
memory: 28904kb

input:

500 10000
abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...

output:

1 4

result:

ok 

Test #28:

score: 0
Accepted
time: 81ms
memory: 29072kb

input:

500 10000
abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...

output:

1 4

result:

ok 

Test #29:

score: 0
Accepted
time: 243ms
memory: 29112kb

input:

500 10000
acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...

output:

1 2

result:

ok 

Test #30:

score: 0
Accepted
time: 424ms
memory: 28988kb

input:

500 10000
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

9997 10000

result:

ok 

Test #31:

score: 0
Accepted
time: 22ms
memory: 28900kb

input:

500 10000
aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 4

result:

ok 

Test #32:

score: 0
Accepted
time: 26ms
memory: 28968kb

input:

500 10000
aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 10000

result:

ok 

Test #33:

score: 0
Accepted
time: 283ms
memory: 28904kb

input:

500 10000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

6001 10000

result:

ok 

Test #34:

score: 0
Accepted
time: 354ms
memory: 28948kb

input:

500 10000
abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

8189 10000

result:

ok 

Test #35:

score: 0
Accepted
time: 873ms
memory: 54420kb

input:

500 20000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

18001 20000

result:

ok 

Test #36:

score: 0
Accepted
time: 771ms
memory: 54292kb

input:

500 20000
abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

16381 20000

result:

ok