Today, Osama gave Fadi an integer $X$, and Fadi was wondering about the minimum possible value of $max(a, b)$ such that $LCM(a, b)$ equals $X$. Both $a$ and $b$ should be positive integers.

$LCM(a, b)$ is the smallest positive integer that is divisible by both $a$ and $b$. For example, $LCM(6, 8) = 24$, $LCM(4, 12) = 12$, $LCM(2, 3) = 6$.

Of course, Fadi immediately knew the answer. Can you be just like Fadi and find any such pair?


-----Input-----

The first and only line contains an integer $X$ ($1 \le X \le 10^{12}$).


-----Output-----

Print two positive integers, $a$ and $b$, such that the value of $max(a, b)$ is minimum possible and $LCM(a, b)$ equals $X$. If there are several possible such pairs, you can print any.


-----Examples-----
Input
2

Output
1 2

Input
6

Output
2 3

Input
4

Output
1 4

Input
1

Output
1 1

Difficulty: interview

Starter code:

Solutions:
import math
x = int(input())

ans = 10**13
ab = [1, 1]
for i in range(1, int(x**(1/2))+1):
    if x % i == 0:
        a = x//i
        b = i

        g = math.gcd(a, b)
        a *= g
        b *= g
        if ans > max(a, b):
            ans = max(a, b)
            ab = [a, b]

print(ab[0], ab[1])


import math

def lcm(a,b):
    g = math.gcd(max(a,b),min(a,b))
    return a*b//g

def main():
    x = int(input())
    facts = []
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            facts.append([i,x//i])

    min_val = float('inf')
    a = -1
    b = -1
    for i in facts:
        if max(i) < min_val and lcm(i[0],i[1]) == x:
            min_val = max(i)
            a = i[0]
            b = i[1]

    print(a,b)

main()


from bisect import bisect_left


def gcd(a, b):
    while(b):
        a %= b
        a, b = b, a  # Swap para tener el mas chico en b
    return a


def divisors(n):
    d = []
    for i in range(1, int(n**0.5)+1):
        if (n % i == 0):
            d.append(i) if(i*i == n) else d.extend([i, n//i])
    return list(sorted(d))


def solve():
    n = int(input())
    if n == 1:
        print(1, 1)
        return
    for i in divisors(n):
        if i*i <= n or gcd(i, n//i) > 1:
            continue
        else:
            print(n//i, i)
            return


solve()


import sys
input = sys.stdin.readline

x=int(input())
y=x
ANS=x+1
AX=[0,0]

import math
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1
x=y
LEN=len(FACT)
LIST=list(FACT.keys())
for i in range(1<<LEN):
    sc=1
    for j in range(LEN):
        if i & (1<<j) !=0:
            sc*=LIST[j]**FACT[LIST[j]]

    if ANS>max(sc,x//sc):
        ANS=max(sc,x//sc)
        AX=[sc,x//sc]

print(*AX)


from math import gcd
x=int(input())
ans=10**18
for i in range(1,int(x**.5)+1):
    if x%i==0:
        if gcd(i,x//i)==1:
            if max(i,x//i)<ans:
                ans=max(i,x//i)
                w=[i,x//i]
print(*w)

def gcd(a, b):
    if(b == 0):
        return a
    else:
        return gcd(b, a % b)


n = int(input())
a, b = 1, n
for i in range(2, n):
    if i*i > n:
        break
    if n % i == 0 and gcd(i, n//i) == 1:
        a, b = i, n//i
print(a, b)


from math import gcd

x = int(input())
for n in range(int(x**0.5),0,-1):
    if x%n == 0 and gcd(n, x//n)==1:
        print(n, x//n)
        break