CF1366D.Two Divisors

You are given $n$ integers $a_1, a_2, \dots, a_n$.

For each $a_i$ find its two divisors $d_1 \gt 1$ and $d_2 \gt 1$ such that $\gcd(d_1 + d_2, a_i) = 1$ (where $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$) or say that there is no such pair.

给你 $n$ 个整数 $a_1, a_2, \dots, a_n$。

对每个 $a_i$，找出它的两个大于 $1$ 的因数 $d_1 > 1$ 和 $d_2 > 1$，使得 $\gcd(d_1 + d_2, a_i) = 1$（其中 $\gcd(a, b)$ 表示 $a$ 与 $b$ 的最大公约数）；若不存在这样的数对，则说明不存在。

The first line contains single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the size of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 10^7$) — the array $a$.

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）——数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \le a_i \le 10^7$）——数组 $a$。

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

The $i$-th integers in the first and second lines should be corresponding divisors $d_1 \gt 1$ and $d_2 \gt 1$ such that $\gcd(d_1 + d_2, a_i) = 1$ or $-1$ and $-1$ if there is no such pair. If there are multiple answers, print any of them.

为了加快输出速度，请输出两行，每行包含 $n$ 个整数。

第一行和第二行的第 $i$ 个整数应分别为满足 $\gcd(d_1 + d_2, a_i) = 1$ 的对应因子 $d_1 \gt 1$ 和 $d_2 \gt 1$；若不存在这样的数对，则输出 $-1$。若存在多个答案，输出任意一个即可。

Let's look at $a_7 = 8$. It has $3$ divisors greater than $1$: $2$, $4$, $8$. As you can see, the sum of any pair of divisors is divisible by $2$ as well as $a_7$.

There are other valid pairs of $d_1$ and $d_2$ for $a_{10}=24$, like $(3, 4)$ or $(8, 3)$. You can print any of them.

我们来看 $a_7 = 8$。它有 $3$ 个大于 $1$ 的约数：$2$、$4$、$8$。如你所见，任意两个约数之和既能被 $2$ 整除，也能被 $a_7$ 整除。

对于 $a_{10}=24$，还存在其他满足条件的约数对 $(d_1, d_2)$，例如 $(3, 4)$ 或 $(8, 3)$。你可以输出其中任意一个。