Bit (xüsusi) sətirləri təhlil edərkən
Sizcə, sətirləri təhlil etmək asandır? Bəli, amma yalnız yuxuda deyilsinizsə. Ancaq siz yatırsınız və yuxu görürsünüz. Gözlənilməz, elə deyilmi? Amma... mən qorxuram ki, bu, olmaq istədiyiniz yuxu deyil. Yuxunuzda bitlərdən ibarət bir sıra var, uzun bir bitlər sırası, hansıyla ki, məşğul olmalısınız. Və siz dəqiq başa düşürsünüz ki, bu dəhşətli yuxudan dərhal çıxmaq üçün nə etmək lazımdır: ən yaxşı xüsusi sətiri tapmaq lazımdır.
Xoşbəxtlikdən, dünən xüsusi sətirlərin nəzəriyyəsi haqqında bir kitab oxudunuz. Siz yalnız xüsusi sətirlərin qəribə tərifini xatırlaya bildiniz, hansı ki, belə görünürdü.
Tutaq ki, sizdə n uzunluğunda bitlərdən ibarət T sırası var. T bitlərini T_1, T_2, ..., T_n ilə işarə edək. A(i, j) və B(i, j) ilə T_i, T_{i+1}, ..., T_{j} arasında müvafiq olaraq 0-bitlərinin və 1-bitlərinin sayını işarə edək. T sırası xüsusi adlanır, əgər 1 ilə n arasında hər bir i üçün aşağıdakı əlaqə yerinə yetirilirsə: A(1, i) ≥ B(1, i) və A(i, n) ≤ B(i, n).
Lakin sizi hər hansı bir xüsusi sıra qane etmir. Sizə ən yaxşı xüsusi sıra lazımdır. Yuxu çox qəribə idi, buna görə də hansı sətirin daha yaxşı olduğunu müəyyən edən qayda da çox qəribə görünür. Tutaq ki, L_1 və L_2 iki sətirin uzunluqlarıdır, P_1 və P_2 isə onların giriş sətiri S-də alt sətir kimi neçə dəfə rast gəldiklərini göstərir. Birinci sıra ikinci sıradan daha yaxşı hesab olunur, əgər L_1∙P_1 > L_2∙P_2.
Beləliklə, sizin tapşırığınız sadədir... ya yox? Ən yaxşı xüsusi sətiri tapın - elə bir xüsusi sıra ki, digər xüsusi sətirlərdən heç biri ondan daha yaxşı deyil.
Giriş verilənləri
Bir sətir S (2 ≤ |S| ≤ 2*10^5), hansı ki, sıfırlardan və birlərdən ibarətdir.
Çıxış verilənləri
Birinci sətir L∙P dəyərini ehtiva etməlidir, burada L ən yaxşı xüsusi sətirin uzunluğu, P isə onun S-də alt sətir kimi neçə dəfə rast gəldiyini göstərir. İkinci sətir isə həmin ən yaxşı sətiri ehtiva etməlidir. Əgər belə bir neçə varsa, istənilən birini çıxarın.
Zəmanət verilir ki, ən azı bir xüsusi sıra S-də alt sətir kimi mövcuddur.