时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $A$，请对它们的乘积 $X=A_1\times A_2\times \dots\times A_n$ 进行因式分解。

格式

输入格式

第一行包含一个整数 $n$，表示数组 $A$ 的长度。

第二行包含 $n$ 个整数 $A_i$。

输出格式

以 $p_1\ k_1\ p_2\ k_2\dots$ 的形式输出 $X$ 的因式分解结果，其中 $p_i$ 是按从小到大顺序排列的 $X$ 的质因数，$k_i$ 是 $p_i$ 对应的指数。

样例

样例输入 #1

4
9 6 4 14

样例输出 #1

2 4 3 3 7 1

样例解释 #1

$X=9\times 6\times 4\times 14=3024$。

因式分解结果为 $3024=2^4\times 3^3\times 7^1$。

数据规模

对于 $20\%$ 的数据， $n=1$。

对于 $40\%$ 的数据， $n\leq 2$。

对于 $100\%$ 的数据， $1\leq n\leq 10^4$， $2\leq A_i\leq 10^6$。