Космонавт Наташа полетела исследовать Марс. Она знала, что марсиане — очень бедные инопланетяне. Чтобы обеспечить лучшую жизнь для своих граждан, их император решил брать налог с каждого туриста, посетившего планету. Наташа — жительница Земли, поэтому, чтобы попасть на территорию Марса, ей пришлось заплатить налог.
На Марсе существуют \(n\) номиналов банкнот: \(i\)-й номинал равен \(a_i\). У Наташи есть бесконечное количество купюр каждого номинала.
На руке каждого марсианина находится \(k\) пальцев, поэтому на Марсе используется система счисления с основанием \(k\). Кроме того, марсиане считают цифру \(d\) (в системе счисления с основанием \(k\)) божественной. В связи с этим, если последняя цифра в записи суммы налога Наташи в системе счисления с основанием \(k\) будет \(d\), марсиане будут счастливы. К сожалению, Наташа пока не знает божественную цифру марсиан.
Определите, при каких значениях \(d\) Наташа сможет сделать марсиан счастливыми.
Наташа может использовать только свои банкноты. Марсиане ей не дают сдачу.
Выходные данные
В первой строке выведите количество значений \(d\), при которых Наташа сможет сделать марсиан счастливыми.
Во второй строке выведите все эти значения в возрастающем порядке.
Все числа выводите в десятичной системе счисления.
Примечание
Рассмотрим первый тестовый пример. В нём используется восьмеричная система счисления.
Возьмём одну купюру номиналом \(12\). В восьмеричной системе счисления это \(14_8\). Последняя цифра — \(4_8\).
Возьмём одну купюру номиналом \(12\) и одну купюру номиналом \(20\). Сумма — \(32\). В восьмеричной системе счисления это \(40_8\). Последняя цифра — \(0_8\).
Возьмём две купюры номиналом \(20\). Сумма — \(40\). В восьмеричной системе счисления это \(50_8\). Последняя цифра — \(0_8\).
Никакую другую цифру, кроме \(0_8\) и \(4_8\), получить нельзя. Цифры \(0_8\) и \(4_8\) можно также получить и другими способами.
Во втором тестовом примере используется десятичная система счисления. Номиналы всех купюр заканчиваются нулём, поэтому Наташа может дать марсианам только сумму, десятичная запись которой тоже заканчивается нулём.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 8
12 20
|
2
0 4
|
|
2
|
3 10
10 20 30
|
1
0
|