Задачи
Факторизация
Факторизация
Однажды вечерком к нам в гости зашел математик Петров Н.Н. Он копался в исходниках PGP (version 0.000001) и обнаружил в реализации алгоритма генерации открытого ключа одной очень известной криптографической системы недоработку.
Ключ в этой системе является произведением двух больших простых чисел, не равных друг другу. Петров утверждает, что если числа отличаются незначительно, то разложить ключ не представляет труда. Программист, написавший модуль к PGP, при генерации ключа не учел этого, он только проверил, что множители различны.
Вам задано число \textbf{n}, представляющее собой произведение двух простых чисел \textbf{p} и \textbf{q}.
Ваша задача -- найти эти числа.
\InputFile
В первой и единственной строке входного файла записано натуральное число \textbf{n} (\textbf{10^98} ≤ \textbf{n} ≤ \textbf{10^102}).
\OutputFile
\includegraphics{https://static.e-olymp.com/content/39/3995b40544e525d376185586daa9f99a529da162.jpg}
Если окажется, что , то выведите в выходной файл строку "\textbf{Impossible}" (без кавычек). В противном случае в первой строке выходного файла выведите меньший множитель, а во второй строке -- больший.
Входные данные #1
7934870381945864918905297081473760990739701202397683128574937380029499574504155950432196212581315823
Выходные данные #1
Impossible