J. Saki and Decryption
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Saki successfully intercepted the secret communication of queerats, but the information is encrypted.

It is known that, for some unknown primes $$$p$$$ and $$$q$$$ with $$$2^{100} \le p, q \lt 2^{150}$$$ such that $$$2p-1$$$ and $$$2p^2-2p+1$$$ are both primes, queerats uses $$$N = p(2p-1)(2p^2-2p+1)q^2$$$ to encrypt their message.

Whether Saki can decrypt the message or not depends on whether she can recover $$$p$$$ and $$$q$$$. Write a program to help Saki recover $$$p$$$ and $$$q$$$ given $$$N$$$. Your solution will be tested against exactly 50 fixed testcases, including the sample tests.

Input

The input is given in the following format:

$$$N$$$

The input satisfies the following constraints:

  • All numbers in the input are integers.
  • $$$N$$$ is constructed as decribed in the problem statement.
Output

The output should be in the following format:

$$$p$$$$$$q$$$

It can be proved that $$$p$$$ and $$$q$$$ is uniquely determined under the constraints of this problem.

Examples
Input
30958404678287761871650278141363... (truncated because too long)
Output
27519497234739335217702161486538475049927611 3673485247907112592302554948506673
Input
2637606013846171358319274548523376... (truncated because too long)
Output
1770172552826549812180151791951 259145553434053480260418032745896979495962091