Số chính phương gần nhất - EP1 (Nearest Perfect Square - EP1)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một số nguyên dương được gọi là số chính phương nếu nó là bình phương của một số nguyên dương. Ví dụ, $1,4,9,16,25$ là các số chính phương.

Cho số nguyên dương $N$. Với mỗi số chính phương $S$, khoảng cách từ $S$ đến $N$ là $|N-S|$.

Hãy tìm số chính phương $S$ có khoảng cách nhỏ nhất đến $N$, đồng thời tính khoảng cách nhỏ nhất $D=|N-S|$.

Input

Một dòng chứa số nguyên dương $N$.

Output

In hai số nguyên $S$ và $D$, trong đó $S$ là số chính phương gần $N$ nhất và $D=|N-S|$.

Subtask

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

Ví dụ

Ví dụ 1

Input

20

Output

16 4

Giải thích

$4^2=16$ và $5^2=25$ là hai số chính phương kề hai phía của 20. Ta có $20-16=4$ và $25-20=5$, nên số gần nhất là 16 và khoảng cách nhỏ nhất là 4.

Ví dụ 2

Input

24

Output

25 1

Giải thích

$25=5^2$ và $|24-25|=1$, vì vậy kết quả là 25 1.

Ví dụ 3

Input

30

Output

25 5

Giải thích

Hai bình phương kề 30 là $25=5^2$ và $36=6^2$. Hai khoảng cách là 5 và 6, nên chọn 25.

Ví dụ 4

Input

81

Output

81 0

Giải thích

$81=9^2$ đã là số chính phương nên khoảng cách nhỏ nhất bằng 0.

Ví dụ 5

Input

999999999999999999

Output

1000000000000000000 1

Giải thích

$10^{18}=(10^9)^2$ và chỉ lớn hơn $N$ đúng 1, nên đây là số chính phương gần nhất.