Under construction

Still being built. Things may change

Etched Emerald Orbs

Time limit3sMemory limit1024 MB

Summary
Given k, find x < y with 2/k = 1/x + 1/y and the smallest x + y, or report -1 if no such pair exists.
Level

Medium6 of 10

Topics
Number theory, Math
Solved
No attempts yet

Problem

An archaeologist team found a tomb of the ancient tribe and discovered 21252^{125} emerald orbs inside the tomb. The ancient tribe etched a number on each emerald orb. The archaeologists spent two decades realizing that each emerald orb has a unique number. The numbers run from 11 to 21252^{125}, written in the ancient language.

Eddy, the only mathematician on the archaeologist team, recently figured out the relation between the number kk and the emerald orb numbered kk. The weight of the emerald orb numbered kk is exactly 1k\frac{1}{k} grams. Since every orb has a distinct number, no two orbs have the same weight.

Eddy proposes a hypothesis: the ancient tribe used these orbs to represent weights less than 11 gram. Clearly the orb numbered kk represents 1k\frac{1}{k} gram. Eddy then tries to represent 2k\frac{2}{k} grams for 3≤k≤4×10183 \le k \le 4 \times 10^{18} with two orbs. He finds that the orbs numbered 22 and 66 represent 23=12+16\frac{2}{3} = \frac{1}{2} + \frac{1}{6} grams. Similarly, the orbs numbered 33 and 1515 represent 25=13+115\frac{2}{5} = \frac{1}{3} + \frac{1}{15} grams.

Write a program that checks whether two orbs can represent 2k\frac{2}{k} grams for a given integer kk. If several pairs of orbs represent 2k\frac{2}{k} grams, output the pair that minimizes the sum of the numbers on them. If no pair exists, output −1-1.

Input

The input contains one positive integer kk.

Output

If there is no solution, output −1-1. Otherwise, output two distinct integers xx and yy separated by a space, where 2k=1x+1y\frac{2}{k} = \frac{1}{x} + \frac{1}{y} and 1≤x<y≤21251 \le x < y \le 2^{125}. If there are multiple solutions, output the one that minimizes x+yx + y.

Constraints

3≤k≤4×10183 \le k \le 4 \times 10^{18}.

Examples2

  1. Example 1

    Input
    5
    
    Expected output
    3 15
    
  2. Example 2

    Input
    7
    
    Expected output
    4 28