Difference of Squares

Interview

Time limit1sMemory limit512 MB

Summary

Given n up to 2^60, find positive integers x and y with x^2 - y^2 = n, or report that none exist.

Level: Medium4 of 10
Topics: Math, Number theory, Implementation, Brute force
Solved: No attempts yet

Problem

You are taking part in the development of a software module for a computer algebra system. The module will be used to solve Diophantine equations of a special form.

For a given non-negative integer n, the module under development must find two positive integers x and y such that x2 − y2 = n. The numbers found must not exceed 262 − 1.

Write a program that, for a given non-negative integer n, finds positive integers x and y not exceeding 262 − 1 whose difference of squares equals n.

Input

The single line contains one integer n (0 ≤ n ≤ 260).

Note that the number in the input does not fit in a 32-bit data type, so you must use a 64-bit data type (for example, «long long» in C++, «int64» in Pascal, «long» in Java).

Output

If the required x and y exist, print two lines: on the first line print the word «Yes», and on the second line print the required x and y.

If there are several suitable pairs x and y, you may print any of them, but the condition 1 ≤ x, y ≤ 262 − 1 must hold.

If there is no solution, print the word «No» on a single line.

Examples2

Example 1
Input
```
3
```
Expected output
```
Yes
2 1
```
Example 2
Input
```
2
```
Expected output
```
No
```