CF1366D Two Divisors

给定 $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$ 的最大公约数），或者说明不存在这样的因子对。

第一行包含一个整数 $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$。

为了加快输出速度，请输出两行，每行包含 $n$ 个整数。 第一行和第二行的第 $i$ 个整数分别为对应的因子 $d_1 > 1$ 和 $d_2 > 1$，满足 $\gcd(d_1 + d_2, a_i) = 1$，如果不存在这样的因子对，则输出 $-1$ 和 $-1$。如果有多组答案，输出任意一组均可。

以 $a_7 = 8$ 为例。它有 $3$ 个大于 $1$ 的因子：$2$、$4$、$8$。可以看到，任意一对因子的和都能被 $2$ 整除，同时 $a_7$ 也能被 $2$ 整除，因此不存在满足条件的因子对。 对于 $a_{10}=24$，存在其他合法的 $d_1$ 和 $d_2$，如 $(3, 4)$ 或 $(8, 3)$。你可以输出任意一组。 由 ChatGPT 4.1 翻译