Задача №113684. Бактерии
У юного биолога Антона в красивой стеклянной колбе живут \(n\) бактерий.
Добавляя различные реактивы в колбу, Антон может контролировать число бактерий. Так, если \(p\) — некоторое простое число, то Антон умеет в домашних условиях получать вещество \(C_pH_{2p \ + \ 1}OH\), которое, будучи добавленным в колбу, уменьшает число бактерий ровно в \(p\) раз. Если же число бактерий не делилось на \(p\), то результат действия вещества не определен, и эксперимент теряет научную точность. Этого Антон допустить не желает, поэтому он применяет вещество \(C_pH_{2p \ + \ 1}OH\) только когда число бактерий делится на p.
Кроме того, у Антона на кухне есть неограниченный запас диэтиламида лизергиновой кислоты (\(C_{20}H_{25}N_{30}\)). При добавлении в колбу с бактериями диэтиламида лизергиновой кислоты, число бактерий возводится в квадрат.
Антон хочет, чтобы в колбе стало \(m\) бактерий. При этом он хочет добавлять какие-либо вещества в колбу наименьшее возможное число раз. Помогите ему сделать это.
Во входном файле содержатся два натуральных числа \(n\) и \(m\) (\(1 \le n, m \le 10^9\) ) — изначальное и желаемое число бактерий в колбе у Антона.
Если получить ровно m бактерий невозможно, выведите в выходной файл слово «Impossible».
Если же искомый результат достижим, выведите кратчайшую последовательность добавлений веществ, которая позволяет его достичь, в следующем формате: добавление вещества \(C_pH_{2p \ + \ 1}OH\) кодируется числом \(p\), добавление вещества \(C_{20}H_{25}N_{30}\) — числом \(0\). Числа должны быть разделены пробелами и/или переводами строк.
Если существует несколько кратчайших последовательной добавлений веществ, оставляющих \(m\) бактерий, выведите любую из них.
В первом примере Антону требуется добавлять в колбу вещества три раза: сначала добавить \(C_2H_5OH\), уменьшая число бактерий в два раза, то есть оставляя \(6\) бактерий; затем добавить \(C_{20}H_{25}N_{30}\), возводя число бактерий в квадрат, то есть увеличивая его до \(36\); и наконец, добавить снова \(C_2H_5OH\), деля число бактерий на два и делая его равным \(18\).
12 18
2 0 2
56 6
Impossible