Sərhəd sehrləri
Sehrbaz Merlin Uzaq Krallığın sərhədini qorumaq üçün yeni bir sehr hazırlayır. Bu sehrin daha ətraflı təhlili üçün Merlin sehrin sehrli kodunu öyrənməyə və onu sehr kitablarında tövsiyə olunanlarla müqayisə etməyə qərar verib.
Sehr w uzunluğu n olan, kiçik latın hərfləri ilə yazılmış sehrli runlardan ibarət bir sözdür. Biz deyəcəyik ki, sehr qeyri-trivialdır, əgər onun boş olmayan prefiksi varsa, bu prefiks bütün sehrdən fərqli olmalı və eyni zamanda onun sonluğu olmalıdır. Məsələn, "abababa" sehri qeyri-trivialdır, çünki onun prefiksi "ababa" həm də onun sonluğudur, amma "aababab" sehri qeyri-trivial deyil.
Merlin w sehrinin 1-dən n-ə qədər bütün dövri sürüşmələrini nəzərdən keçirir. i-ci dövri sürüşmə başlanğıc sehrin i-ci simvolundan başlayan dövri sürüşmə hesab olunur. Məsələn, "abababa" sehrinin birinci dövri sürüşməsi "abababa", ikinci isə "bababaa" və s., yeddinci dövri sürüşmə isə "aababab" bərabərdir.
Sehrin w sehrli kodu B(w) ilə işarələnir və n ədəd "0" və "1" simvollarından ibarət bir sözdür. Bu zaman i-ci simvol B(w) "1" bərabərdir, əgər i-ci dövri sürüşmə w qeyri-trivialdırsa, və "0" əks halda. Məsələn, "abababa" sehrinin sehrli kodu "1011110" bərabərdir.
Verilmiş sehr w üçün onun sehrli kodunu tapmaqda Merlina kömək edin.
Giriş məlumatları
Girişdə kiçik latın hərflərindən ibarət olan sehr w verilir. Onun uzunluğu 100000-dən çox deyil.
Çıxış məlumatları
Çıxışa verilmiş sehrin sehrli kodunu yazın.