Numerolodzy z Krainy Trzech Królestw nie mają łatwego życia. Ciągi numerologiczne są tak długie, że ledwo mieszczą się w numerologicznych kajetach, a gdy w rozstrzyganą sprawę zaangażowanych jest wiele osób, często brakuje miejsca na zapisywanie numerologicznych ciągów. Trudno zliczyć tych, którzy z tak błahego powodu jak brak miejsca w kajecie oblali egzamin u legendarnego profesora Tichego na Uniwersytecie Numerologicznym Cabana Sabiego w Kyvkubie (oczywiście mniej niż tych, którzy nie zdali przez niechodzenie na wykłady, ale brak miejsca w kajecie jakoś bardziej utrwalił się w społecznej świadomości). Na szczęście numerolodzy zauważyli, że wiele nawet bardzo długich ciągów ma stosunkowo krótki okres (czyli, że niektóre długie ciągi składają się z wielokrotnie powtórzonego stosunkowo krótkiego podciągu).
 
Wejście
 
Program na wejściu otrzymuje się czwórkę a, b, c, d (b<c<d, 0<a < 16000001, d mieści się w typie unsigned int) opisującą pewien ciąg numerologiczny składający się z a cyfr (zer i jedynek). To czy w jakimś miejscu w ciągu znajduje się 0 czy 1 zależy od tego czy na odpowiadającym mu miejscu w tzw ciągu pomocniczym znajduje się wartość większa od b (wartościom większym od b odpowiada 1 , a mniejszym lub równym b odpowiada 0). Ciąg pomocniczy definiujemy w następujący sposób:
 
Pierwszym elementem ciągu pomocniczego jest c.
Kolejne elementu ciągu obliczamy ze wzoru e=d-(z*z mod d)-1, gdzie e to nowy a z poprzedni element ciągu pomocniczego.
Wyjście
 
Program powinien wypisać na wyjściu najkrótszy okres wczytanego na wejściu ciągu
 
Przykład
 
Wejście 1
 
100 1 3 4
Wyjście 1
 
1
Wejście 2
 
10 1 2 3
Wyjście 2
 
1000000000
Wejście 3
 
7 1 3 5
Wyjście 3
 
101

TnVtZXJvbG9kenkgeiBLcmFpbnkgVHJ6ZWNoIEtyw7NsZXN0dyBuaWUgbWFqxIUgxYJhdHdlZ28gxbx5Y2lhLiBDacSFZ2kgbnVtZXJvbG9naWN6bmUgc8SFIHRhayBkxYJ1Z2llLCDFvGUgbGVkd28gbWllc3pjesSFIHNpxJkgdyBudW1lcm9sb2dpY3pueWNoIGthamV0YWNoLCBhIGdkeSB3IHJvenN0cnp5Z2FuxIUgc3ByYXfEmSB6YWFuZ2HFvG93YW55Y2ggamVzdCB3aWVsZSBvc8OzYiwgY3rEmXN0byBicmFrdWplIG1pZWpzY2EgbmEgemFwaXN5d2FuaWUgbnVtZXJvbG9naWN6bnljaCBjacSFZ8Ozdy4gVHJ1ZG5vIHpsaWN6ecSHIHR5Y2gsIGt0w7NyenkgeiB0YWsgYsWCYWhlZ28gcG93b2R1IGphayBicmFrIG1pZWpzY2EgdyBrYWplY2llIG9ibGFsaSBlZ3phbWluIHUgbGVnZW5kYXJuZWdvIHByb2Zlc29yYSBUaWNoZWdvIG5hIFVuaXdlcnN5dGVjaWUgTnVtZXJvbG9naWN6bnltIENhYmFuYSBTYWJpZWdvIHcgS3l2a3ViaWUgKG9jenl3acWbY2llIG1uaWVqIG5pxbwgdHljaCwga3TDs3J6eSBuaWUgemRhbGkgcHJ6ZXogbmllY2hvZHplbmllIG5hIHd5a8WCYWR5LCBhbGUgYnJhayBtaWVqc2NhIHcga2FqZWNpZSBqYWtvxZsgYmFyZHppZWogdXRyd2FsacWCIHNpxJkgdyBzcG/FgmVjem5laiDFm3dpYWRvbW/Fm2NpKS4gTmEgc3pjesSZxZtjaWUgbnVtZXJvbG9kenkgemF1d2HFvHlsaSwgxbxlIHdpZWxlIG5hd2V0IGJhcmR6byBkxYJ1Z2ljaCBjacSFZ8OzdyBtYSBzdG9zdW5rb3dvIGtyw7N0a2kgb2tyZXMgKGN6eWxpLCDFvGUgbmlla3TDs3JlIGTFgnVnaWUgY2nEhWdpIHNrxYJhZGFqxIUgc2nEmSB6IHdpZWxva3JvdG5pZSBwb3d0w7Nyem9uZWdvIHN0b3N1bmtvd28ga3LDs3RraWVnbyBwb2RjacSFZ3UpLgoKV2VqxZtjaWUKClByb2dyYW0gbmEgd2VqxZtjaXUgb3RyenltdWplIHNpxJkgY3p3w7Nya8SZIGEsIGIsIGMsIGQgKGI8YzxkLCAwPGEgPCAxNjAwMDAwMSwgZCBtaWXFm2NpIHNpxJkgdyB0eXBpZSB1bnNpZ25lZCBpbnQpIG9waXN1asSFY8SFIHBld2llbiBjacSFZyBudW1lcm9sb2dpY3pueSBza8WCYWRhasSFY3kgc2nEmSB6IGEgY3lmciAoemVyIGkgamVkeW5laykuIFRvIGN6eSB3IGpha2ltxZsgbWllanNjdSB3IGNpxIVndSB6bmFqZHVqZSBzacSZIDAgY3p5IDEgemFsZcW8eSBvZCB0ZWdvIGN6eSBuYSBvZHBvd2lhZGFqxIVjeW0gbXUgbWllanNjdSB3IHR6dyBjacSFZ3UgcG9tb2NuaWN6eW0gem5hamR1amUgc2nEmSB3YXJ0b8WbxIcgd2nEmWtzemEgb2QgYiAod2FydG/Fm2Npb20gd2nEmWtzenltIG9kIGIgb2Rwb3dpYWRhIDEgLCBhIG1uaWVqc3p5bSBsdWIgcsOzd255bSBiIG9kcG93aWFkYSAwKS4gQ2nEhWcgcG9tb2NuaWN6eSBkZWZpbml1amVteSB3IG5hc3TEmXB1asSFY3kgc3Bvc8OzYjoKClBpZXJ3c3p5bSBlbGVtZW50ZW0gY2nEhWd1IHBvbW9jbmljemVnbyBqZXN0IGMuCktvbGVqbmUgZWxlbWVudHUgY2nEhWd1IG9ibGljemFteSB6ZSB3em9ydSBlPWQtKHoqeiBtb2QgZCktMSwgZ2R6aWUgZSB0byBub3d5IGEgeiBwb3ByemVkbmkgZWxlbWVudCBjacSFZ3UgcG9tb2NuaWN6ZWdvLgpXeWrFm2NpZQoKUHJvZ3JhbSBwb3dpbmllbiB3eXBpc2HEhyBuYSB3eWrFm2NpdSBuYWprcsOzdHN6eSBva3JlcyB3Y3p5dGFuZWdvIG5hIHdlasWbY2l1IGNpxIVndQoKUHJ6eWvFgmFkCgpXZWrFm2NpZSAxCgoxMDAgMSAzIDQKV3lqxZtjaWUgMQoKMQpXZWrFm2NpZSAyCgoxMCAxIDIgMwpXeWrFm2NpZSAyCgoxMDAwMDAwMDAwCldlasWbY2llIDMKCjcgMSAzIDUKV3lqxZtjaWUgMwoKMTAx