Задача L. Целочисленный аттрактор

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

Для заданных натуральных чисел k и q определим последовательность следующего вида: A1 = k, Ai + 1 = Ai + Bi − Ci, где Bi — сумма цифр числа Ai (в системе счисления по основанию q), расположенных на нечетных позициях, а Ci — сумма цифр, расположенных на четных позициях. При этом полагается, что позиции цифр в числе нумеруются слева направо (начиная от старшего ненулевого разряда, которому присваивается 1-й номер).

Обозначим за L(k) наиболее раннюю позицию с которой указанная последовательность начинает повторяться. Иначе говоря, имеет место следующее утверждение: L(k) = min{l: ∀ (i > l)~∃ (j < i): (Aj = Ai)}.

Требуется вычислить последовательность значений L(k) для всех натуральных k ≤ m при некотором фиксированном q.

Формат входного файла

Входной файл "input.txt" содержит пару натуральных чисел: q и m.

Формат выходного файла

Выходной файл "output.txt" должен содержать последовательность значений L(k), расположенных в порядке возрастания величины k = 1, 2, …, m.

Ограничения

0 < m ≤ 106, 2 ≤ q < 232

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 10
6 5 4 4 3 3 3 3 3 2
2
2 10
3 2 1 5 4 1 3 2 1 2

0.111s 0.021s 15