시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 14 | 4 | 4 | 36.364% |
У юного биолога Антона в красивой стеклянной колбе живут $n$ бактерий.
Добавляя различные реактивы в колбу, Антон может контролировать число бактерий. Так, если $p$ --- некоторое простое число, то Антон умеет в домашних условиях получать вещество , которое, будучи добавленным в колбу, уменьшает число бактерий ровно в $p$ раз. Если же число бактерий не делилось на $p$, то результат действия вещества неопределен, и эксперимент теряет научную точность. Этого Антон допустить не желает, поэтому он применяет вещество только когда число бактерий делится на $p$.
Кроме того, у Антона на кухне есть неограниченный запас диэтиламида лизергиновой кислоты (). При добавлении в колбу с бактериями диэтиламида лизергиновой кислоты, число бактерий возводится в квадрат.
Антон хочет, чтобы в колбе стало $m$ бактерий. При этом он хочет добавлять какие-либо вещества в колбу наименьшее возможное число раз. Помогите ему сделать это.
Во входном файле содержатся два натуральных числа $n$ и $m$ ($1 \le n, m \le 10^9$) --- изначальное и желаемое число бактерий в колбе у Антона.
Если получить ровно $m$ бактерий невозможно, выведите в выходной файл слово <<Impossible
>>.
Если же искомый результат достижим, выведите кратчайшую последовательность добавлений веществ, которая позволяет его достичь, в следующем формате: добавление вещества кодируется числом $p$, добавление вещества --- числом 0. Числа должны быть разделены пробелами и/или переводами строк.
Если существует несколько кратчайших последовательной добавлений веществ, оставляющих $m$ бактерий, выведите любую из них.
12 18
2 0 2
56 6
Impossible
В первом примере Антону требуется добавлять в колбу вещества три раза: сначала добавить \ft{}, уменьшая число бактерий в два раза, то есть оставляя 6 бактерий; затем добавить , возводя число бактерий в квадрат, то есть увеличивая его до 36; и наконец, добавить снова \ft{}, деля число бактерий на два и делая его равным 18.