За первое место на олимпиаде Лёше подарили много массивов целых чисел, уверив его, что эти массивы очень дорогие. Сразу после награждения Лёша принял решение продать их. На двери пункта приема массивов было сказано, что принимаются только массивы, которые можно сжать в генератор, работающий по следующему принципу:
На вход генератору дается четверка целых чисел \(n\), \(m\), \(c\), \(s\), при этом \(n\) и \(m\) положительны, \(s\) неотрицательно, а для \(c\) верно, что \(0 \leq c < m\). Массив \(a\) из \(n\) элементов генерируется по следующим правилам:
- \(a_1 = s \bmod m\), где \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\);
- \(a_i = (a_{i-1} + c) \bmod m\) для всех \(i\) таких, что \(1 < i \le n\).
Например, если \(n = 5\), \(m = 7\), \(c = 4\), а \(s = 10\), то \(a = [3, 0, 4, 1, 5]\).
Цена такого массива вычисляется очень просто — это значение \(m\) в этой четверке чисел.
Лёше стало интересно, сколько денег он может потребовать за каждый свой массив. Помогите Лёше определить для каждого массива, можно ли его задать какой-нибудь четверкой чисел \(n\), \(m\), \(c\), \(s\), и, если да, найти максимальное значение \(m\) среди всех подходящих четверок.