You have a flask containing n live bacteria.
By adding various reagents to the flask, you can control the number of bacteria. If you add 1 mole of CpH2p+1OH into the flask for any prime number p, the number of bacteria will be reduced in exactly p times. If the number of bacteria is not divisible by p, the result is undefined and something bad may happen, e.g. all bacteria die, or the Earth explodes.
In addition, when adding 1 mole of lysergic acid diethylamide (C20H25N3O) to the flask, the number of bacteria is squared.
Now you have unlimited supply of all the substances, and you want to have m bacteria in the flask. What is the minimum number of mole of substances you have to add to the flask?
Warn: 本題有 specialjudge
The input file contains multiple test cases, each on one line. Each line consists of two positive integers n and m (1<= n,m<= 109), indicating the original and the desired number of bacteria.
Please output one line per test case. If you are not able to have exactly m bacteria in the end, output the word "Impossible" in one line. Otherwise, output the shortest sequence of substance additions to achieve the desired result in the following format: adding substance CpH2p+1OH is coded as number p, and adding substance C20H25N3O is coded as number 0. The numbers should be separated by a whitespace. If there are multiple shortest sequences, you may output any of them.
12 18 56 6
2 0 2 Impossible
Migrated from old NTUJ.
St. Petersburg Olympiad team programming 2010
| No. | Testdata Range | Score |
|---|