Problem description

Dany jest zbiór liczb naturalnych S mocy N. Elementy zbioru S₁, S₂, …, S_N generowane są przez liniowy generator zadany parametrami (x,a,c,m):
S₁ = x oraz S_i + 1 = (a⋅S_i+c) mod  m

Napisz program, który: wczyta parametry generatora, wyznaczy parę elementów, których największy wspólny dzielnik jest największy możliwy i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się pięć nieujemnych liczb całkowitych N, x, a, c, m, pooddzielanych pojedynczymi odstępami.

Gwarantowane jest, że wygenerowane przez generator elementy są parami różne oraz, że generator nigdy nie wygeneruje liczby 0.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna - największy możliwy wspólny dzielnik pary liczb ze zbioru S.

Ograniczenia

2 ≤ N ≤ 30 000,

3 ≤ m ≤ 10¹⁵,

1 ≤ x < m,  1 ≤ a < m,  0 ≤ c < m.

Przykład

7 1 2 3 71

5