Nearest Perfect Square - EP1

Version: Phuoc Hung OJ Extended

Problem Statement

A positive integer is called a perfect square if it is the square of a positive integer. For example, $1,4,9,16,25$ are perfect squares.

You are given a positive integer $N$. For each perfect square $S$, define its distance to $N$ as $|N-S|$.

Find the perfect square $S$ with minimum distance to $N$, and also output the minimum distance $D=|N-S|$.

Input

One line containing the positive integer $N$.

Output

Print two integers $S$ and $D$, where $S$ is the perfect square closest to $N$ and $D=|N-S|$.

Subtasks

• Subtask 1 (30 points): $1 \le N \le 10^6$.
• Subtask 2 (30 points): $1 \le N \le 10^{12}$.
• Subtask 3 (40 points): $1 \le N \le 10^{18}$.

Examples

Example 1

Input

20

Output

16 4

Explanation

The two perfect squares around 20 are $4^2=16$ and $5^2=25$. Their distances are 4 and 5, so the answer is 16 with distance 4.

Example 2

Input

24

Output

25 1

Explanation

$25=5^2$ and $|24-25|=1$, so the answer is 25 1.

Example 3

Input

30

Output

25 5

Explanation

The adjacent perfect squares are $25=5^2$ and $36=6^2$. Their distances are 5 and 6, so 25 is closer.

Example 4

Input

81

Output

81 0

Explanation

$81=9^2$ is already a perfect square, so the minimum distance is 0.

Example 5

Input

999999999999999999

Output

1000000000000000000 1

Explanation

$10^{18}=(10^9)^2$ is exactly one greater than $N$, so it is the closest perfect square.