Problem B
Pollard's p-1 Algorithm

Use Pollard’s $p-1$ algorithm to find a non-trivial factor of an integer $n$, using the random number $a=2$ and a boundary $B$. Given a boundary $B$, the problem expects it to be an inclused boundary, i.e., $a^{B!}$ should be computed before we decide no solution is found.

Input

First line consist of an integer $2 \leq n \leq 2^{63}-1$. The second line consist of an integer $1 \leq B \leq 10^5$, the boundary.

Output

Output any non-trivial factor of $n$ or $-1$ if none is found.

144948923
10

7

675103487
50000

-1