RSA Factorization

Time limit1sMemory limit128 MB

Summary

Given a huge n up to 10^120 and k, find primes p ≤ q with n = p*q and |q - kp| bounded by 10^5, requiring advanced factorization insight.

Level: Hard9 of 10
Topics: Number theory, Math, Binary search
Solved: No attempts yet

Problem

Given positive integers $n$ and $k$ , write a program that finds prime numbers $p$ and $q$ such that $n = p \times q$ , $p \le q$ , and $|q - kp| \le 10^5$ .

Input

The first line contains $n$ and $k$ ( $1 < n < 10^{120}$ , $1 < k < 10^8$ ).

Output

On the first line, print the prime numbers $p$ and $q$ that satisfy the conditions, in the form p * q.

Examples1

Example 1
Input
```
35 1
```
Expected output
```
5 * 7
```