链接：https://codeforces.com/contest/1366/problem/D

You are given nn integers a1,a2,…,ana1,a2,…,an.

For each aiai find its two divisors d1>1d1>1 and d2>1d2>1 such that gcd(d1+d2,ai)=1gcd(d1+d2,ai)=1 (where gcd(a,b)gcd(a,b) is the greatest common divisor of aa and bb) or say that there is no such pair.

Input

The first line contains single integer nn (1≤n≤5⋅1051≤n≤5⋅105) — the size of the array aa.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (2≤ai≤1072≤ai≤107) — the array aa.

Output

To speed up the output, print two lines with nn integers in each line.

The ii-th integers in the first and second lines should be corresponding divisors d1>1d1>1 and d2>1d2>1 such that gcd(d1+d2,ai)=1gcd(d1+d2,ai)=1&nbs***bsp;−1−1 and −1−1 if there is no such pair. If there are multiple answers, print any of them.

Example

input

Copy

10
2 3 4 5 6 7 8 9 10 24

output

Copy

-1 -1 -1 -1 3 -1 -1 -1 2 2 
-1 -1 -1 -1 2 -1 -1 -1 5 3

Note

Let's look at a7=8a7=8. It has 33 divisors greater than 11: 22, 44, 88. As you can see, the sum of any pair of divisors is divisible by 22 as well as a7a7.

There are other valid pairs of d1d1 and d2d2 for a10=24a10=24, like (3,4)(3,4)&nbs***bsp;(8,3)(8,3). You can print any of them.

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200000+10,M=1e4+5,mod=1e9+7;
ll n,t,m,x,r,s,u,v,y;
ll a[500001],b[500001],c[500001];
ll vis[10000001];
int main()
{
	cin>>n;
	s=0;
	for(int i=2;i<=10000;i++)
    {
        if(vis[i]==0)
        {
            for(int j=i*2;j<=10000000;j+=i)
            {
                vis[j]=i;
            }
        }
    }
	for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(vis[a[i]]==0)
        {
            b[i]=-1;
            c[i]=-1;
        }
        else
        {
            b[i]=a[i];
            ll p=vis[a[i]];
            c[i]=1;
            while(b[i]%p==0)
            {
                b[i]/=p;
                c[i]*=p;
            }
            if(b[i]==1)
            {
                b[i]=-1;
                c[i]=-1;
            }

        }
    }
    for(int i=1;i<=n;i++)
        cout<<b[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
        cout<<c[i]<<" ";
    cout<<endl;

}