Problem: 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 ≤ X ≤ 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

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
	
public class Cp {
	
//	[2, 5, 7, 13, 17, 29]
//	[3, 11, 19, 23, 31]
	
//	[2, 5, 11, 17, 23, 31]
//	[3, 7, 13, 19, 29]
	public static void main(String[] args) {
		
		long n = sc.nextLong();
		int i = 2;
		long min = n;
		for(i=2;i<(int)Math.sqrt(n)+1;i++) {
			if(n%i==0) {
				if(Math.max(i, n/i)<min && gcd(i,n/i)==1) {
					min = Math.max(i, n/i);
				}
			}
		}
		if(n/min>min) {
			System.out.println(min+" "+n/min);
		}else {
			System.out.println(n/min+" "+min);
		}
	}
	
	
static FastReader sc=new FastReader(); 
static int dp[][];
static int mod=1000000007;

public static long Pow(long base, long exp) {

	 if (exp == 0)
	 return 1;

	 else if (exp == 1)
	 return base;

	 else if (exp%2 == 0)
	 return Pow(base*base, exp/2);

	 else
	 return base*Pow(base, exp-1);
	}
public static long modPow(long base, long exp, long n) {

	 base = base%n;

	 if (exp == 0)
	 return 1;

	 else if (exp == 1)
	 return base;

	 else if (exp%2 == 0)
	 return modPow(base*base%n, exp/2, n);

	 else
	 return base*modPow(base, exp-1, n)%n;
	}

static int go(int A[],int B[],int gcd,int i) {
	if(i==A.length) {
		for(int j=2;j*j<=gcd;j++) {
			if(gcd%j==0) {
				return j;
			}
		}
		return -1;
	}
	
	int g=gcd(A[i],gcd);
	int h=gcd(B[i],gcd);
	int op1=go(A, B, g, i+1);
	if(op1==-1) {
		op1=go(A, B, h, i+1);
		return op1;
	}
	else
		return op1;
}
static int[] input(int n) {
	int A[]=new int[n];
	for(int i=0;i<n;i++) {
		A[i]=sc.nextInt();
	}
	return A;
}
static long[] inputL(int n) {
	long A[]=new long[n];
	for(int i=0;i<n;i++) {
		A[i]=sc.nextLong();
	}
	return A;
}
static String[] inputS(int n) {
	String A[]=new String[n];
	for(int i=0;i<n;i++) {
		A[i]=sc.next();
	}
	return A;
}
static long sum(int A[]) {
	long sum=0;
	for(int i : A) {
		sum+=i;
	}
	return sum;
}
static long sum(long A[]) {
	long sum=0;
	for(long i : A) {
		sum+=i;
	}
	return sum;
}
static void input(int A[],int B[]) {
	for(int i=0;i<A.length;i++) {
		A[i]=sc.nextInt();
		B[i]=sc.nextInt();
	}
}
static int[][] input(int n,int m){
	int A[][]=new int[n][m];
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			A[i][j]=i();
		}
	}
	return A;
}
static char[][] charinput(int n,int m){
	char A[][]=new char[n][m];
	for(int i=0;i<n;i++) {
		String s=s();
		for(int j=0;j<m;j++) {
			A[i][j]=s.charAt(j);
		}
	}
	return A;
}
static int max(int A[]) {
	int max=Integer.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static int min(int A[]) {
	int min=Integer.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long max(long A[]) {
	long max=Long.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static long min(long A[]) {
	long min=Long.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long [] prefix(long A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] prefix(int A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] suffix(long A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static long [] suffix(int A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static long mod(long x) {
	int mod=1000000007;
	return ((x%mod + mod)%mod);
}
static String reverse(String s) {
	StringBuffer p=new StringBuffer(s);
	p.reverse();
	return p.toString();
}

static int i() {
	return sc.nextInt();
}
static String s() {
	return sc.next();
}
static long l() {
	return sc.nextLong();
}  
static void sort(int[] A){
	int n = A.length;
	Random rnd = new Random();
	for(int i=0; i<n; ++i){
		int tmp = A[i];
		int randomPos = i + rnd.nextInt(n-i);
		A[i] = A[randomPos];
		A[randomPos] = tmp;
	}
	Arrays.sort(A);
}
static void sort(long[] A){
	int n = A.length;
	Random rnd = new Random();
	for(int i=0; i<n; ++i){
		long tmp = A[i];
		int randomPos = i + rnd.nextInt(n-i);
		A[i] = A[randomPos];
		A[randomPos] = tmp;
	}
	Arrays.sort(A);
}
static String sort(String s) {
	Character ch[]=new Character[s.length()];
	for(int i=0;i<s.length();i++) {
		ch[i]=s.charAt(i);
	}
	Arrays.sort(ch);
	StringBuffer st=new StringBuffer("");
	for(int i=0;i<s.length();i++) {
		st.append(ch[i]);
	}
	return st.toString();
}
static HashMap<Integer,Integer> hash(int A[]){
	HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
	for(int i : A) {
		if(map.containsKey(i)) {
			map.put(i, map.get(i)+1);
		}
		else {
			map.put(i, 1);
		}
	}
	return map;
}
static TreeMap<Integer,Integer> tree(int A[]){
	TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
	for(int i : A) {
		if(map.containsKey(i)) {
			map.put(i, map.get(i)+1);
		}
		else {
			map.put(i, 1);
		}
	}
	return map;
}
static boolean prime(int n) 
{ 
	if (n <= 1) 
		return false; 
	if (n <= 3) 
		return true; 
	if (n % 2 == 0 || n % 3 == 0) 
		return false; 
	double sq=Math.sqrt(n);
	
	for (int i = 5; i <= sq; i = i + 6) 
		if (n % i == 0 || n % (i + 2) == 0) 
			return false; 
	return true; 
} 
static boolean prime(long n) 
{ 
	if (n <= 1) 
		return false; 
	if (n <= 3) 
		return true; 
	if (n % 2 == 0 || n % 3 == 0) 
		return false; 
	double sq=Math.sqrt(n);
	
	for (int i = 5; i <= sq; i = i + 6) 
		if (n % i == 0 || n % (i + 2) == 0) 
			return false; 
	return true; 
} 
static int gcd(int a, int b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
static long gcd(long a, long b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
static class Pair implements Comparable<Pair>
{
	int x;
	int y;
	Pair(int x,int y){
		this.x=x;
		this.y=y;
	}
	@Override
	public int compareTo(Pair o) {
		if(this.x>o.x)
			return 1;
		else if(this.x<o.x)
			return -1;
		else {
			if(this.y>o.y)
				return 1;
			else if(this.y<o.y)
				return -1;
			else
				return 0;
		}
	}
}
static class FastReader 
{ 
	BufferedReader br; 
	StringTokenizer st; 
	
	public FastReader() 
	{ 
		br = new BufferedReader(new
				InputStreamReader(System.in)); 
	} 
	
	String next() 
	{ 
		while (st == null || !st.hasMoreElements()) 
		{ 
			try
			{ 
				st = new StringTokenizer(br.readLine()); 
			} 
			catch (IOException  e) 
			{ 
				e.printStackTrace(); 
			} 
		} 
		return st.nextToken(); 
	} 
	int nextInt() 
	{ 
		return Integer.parseInt(next()); 
	} 
	
	long nextLong() 
	{ 
		return Long.parseLong(next()); 
	} 
	
	double nextDouble() 
	{ 
		return Double.parseDouble(next()); 
	} 
	
	String nextLine() 
	{ 
		String str = ""; 
		try
		{ 
			str = br.readLine(); 
		} 
		catch (IOException e) 
		{ 
			e.printStackTrace(); 
		} 
		return str; 
	} 
} 



static int multiply(int x, int res[], int res_size) {

	int carry = 0;

	
	for (int i = 0; i < res_size; i++) {
	int prod = res[i] * x + carry;

	
	res[i] = prod % 10;

	carry = prod / 10;
	}


	while (carry > 0) {
	res[res_size] = carry % 10;
	carry = carry / 10;
	res_size++;
	}
	return res_size;
}

public static void power(int x, int n) {
	
	if(n == 0 ){
	System.out.print("1");
	return;
}
	
	int MAX = 1000001;
	int res[] = new int[MAX];
	int res_size = 0;
	int temp = x;

	while (temp != 0) {
	res[res_size++] = temp % 10;
	temp = temp / 10;
	}

	
	for (int i = 2; i <= n; i++)
	res_size = multiply(x, res, res_size);

	System.out.print(x + "^" + n + " = ");
	for (int i = res_size - 1; i >= 0; i--)
	System.out.print(res[i]);
}


}