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