This page is still under construction.

Parts of this page are still being built. What you see may change.

Bacteria

Time limit2sMemory limit512 MB

Summary
Given n and m up to 1e9, find the shortest sequence of operations (squaring, or dividing by a prime) turning n into m, or report impossible.
Level

Medium7 of 10

Topics
Math, Number theory, Greedy, Implementation
Solved
No attempts yet

Problem

Young biologist Anton keeps nn bacteria in a beautiful glass flask.

By adding various reagents to the flask, Anton can control the number of bacteria. If pp is a prime number, Anton can prepare at home a substance that, when added to the flask, reduces the number of bacteria by exactly a factor of pp. If the number of bacteria is not divisible by pp, the effect of the substance is undefined and the experiment loses its scientific accuracy. Anton does not want this, so he applies the substance only when the number of bacteria is divisible by pp.

Anton also has an unlimited supply of lysergic acid diethylamide in his kitchen. When lysergic acid diethylamide is added to the flask with bacteria, the number of bacteria is squared.

Anton wants the flask to contain mm bacteria. He wants to add substances to the flask as few times as possible. Help him do this.

Input

The input file contains two positive integers nn and mm (1≤n,m≤1091 \le n, m \le 10^9), the initial and desired number of bacteria in Anton's flask.

Output

If it is impossible to obtain exactly mm bacteria, print the word <<Impossible>> to the output file.

If the desired result is achievable, print the shortest sequence of substance additions that achieves it in the following format: adding substance is encoded by the number pp, adding substance is encoded by the number 0. The numbers must be separated by spaces and/or newlines.

If there are several shortest sequences of additions leaving mm bacteria, print any one of them.

Hint

In the first example, Anton needs to add substances to the flask three times: first add \ft{}, halving the number of bacteria, leaving 6 bacteria; then add , squaring the number of bacteria, increasing it to 36; and finally add \ft{} again, dividing the number of bacteria by two and making it equal to 18.

Examples2

  1. Example 1

    Input
    12 18
    
    Expected output
    2 0 2
    
  2. Example 2

    Input
    56 6
    
    Expected output
    Impossible