Байтек, славящийся своими необычными подарками, недавно получил в подарок массив целых чисел \(x_0, x_1, \ldots, x_{k-1}\).
К сожалению, после фантастической вечеринки, посвящённой этому массиву, он осознал, что он его потерял. После нескольких часов поисков новой игрушки, Байтек обнаружил на сайте производителя массива \(x\) другой массив \(a\) длины \(n + 1\). Согласно формальному описанию \(a\), \(a_0 = 0\), а для всех остальных \(i\) (\(1 \le i \le n\)) \(a_i = x_{(i-1)\bmod k} + a_{i-1}\), где \(p \bmod q\) обозначает остаток от деления \(p\) на \(q\).
Например, если \(x = [1, 2, 3]\) и \(n = 5\), то:
- \(a_0 = 0\),
- \(a_1 = x_{0\bmod 3}+a_0=x_0+0=1\),
- \(a_2 = x_{1\bmod 3}+a_1=x_1+1=3\),
- \(a_3 = x_{2\bmod 3}+a_2=x_2+3=6\),
- \(a_4 = x_{3\bmod 3}+a_3=x_0+6=7\),
- \(a_5 = x_{4\bmod 3}+a_4=x_1+7=9\).
Таким образом, если \(x = [1, 2, 3]\) и \(n = 5\), то \(a = [0, 1, 3, 6, 7, 9]\).
Байтек надеется, что, зная массив \(a\), он сможет восстановить массив \(x\). Зная, что \(1 \le k \le n\), помогите ему и найдите все возможные значения \(k\) — возможные длины потерянного массива.
Выходные данные
Первая строка выходных данных должна содержать одно целое число \(l\), обозначающее количество подходящих длин потерянного массива.
Вторая строка должна содержать ровно \(l\) целых чисел — возможные длины потерянного массива в возрастающем порядке.
Примечание
В первом примере возможны любые значения \(k\), так как \(a\) является арифметической прогрессией.
Возможны следующие массивы:
- \([1]\)
- \([1, 1]\)
- \([1, 1, 1]\)
- \([1, 1, 1, 1]\)
- \([1, 1, 1, 1, 1]\)
Во втором примере массив Байтека может содержать три или пять элементов.
Возможные массивы \(x\):
- \([1, 2, 2]\)
- \([1, 2, 2, 1, 2]\)
Например, \(k = 4\) не подходит, потому что это приводит к тому, что \(6 + x_0 = 8\) а также \(0 + x_0 = 1\), что является очевидным противоречием.
В третьем примере подходит только \(k = n\).
Массив \([1, 4, -2]\) удовлетворяет всем требованиям.
Обратите внимание, что значения \(x_i\) могут быть отрицательными.