T2 忍者小队

题目信息

时间限制: 1s

空间限制: 512M

输入文件: sor.in

输出文件: sor.out

题目描述

木叶村现役有 $n$ 位忍者，第 $i$ 位忍者的战斗力为 $s_i$，用集合 $S$ 来表示木叶村所有的现役忍者。一支忍者小队可以用集合 $S_0$ 表示，该小队的战斗力为 $S_0$ 中所有忍者的战斗力的最大公约数。

为了方便任务调度，现在火影想知道 $\forall k \in[1, m], \min \left\{\left|S_0\right|\right\}, \max \left\{\left|S_0\right|\right\}$，即如果需要组建一支战斗力为 $k$ 的忍者小队，最少/最多需要多少名忍者。

输入格式

第一行两个正整数 $n, m$，含义如题所示。

第二行 $n$ 个正整数 $S_{1 \sim n}$，表示木叶村现役忍者们的战斗力。

输出格式

输出共 $m$ 行。

对于 $\forall k \in[1, m]$，第 $k$ 行输出两个整数 $a, b$，其中 $a=\min \left\{\left|S_0\right|\right\}, b=\max \left\{\left|S_0\right|\right\}$。如果对于当前的 $k$，无法组成战斗力恰好为 $k$ 的忍者小队，输出两个 -1。

样例

样例输入 1

7 5
30 60 21 42 70 15 30

样例输出 1

3 7
3 5
2 6
-1 -1
2 5

样例输入 2

3 6
2 4 6

样例输出 2

-1 -1
1 3
-1 -1
1 1
-1 -1
1 1

数据范围与提示

对于所有数据, 满足 $1 \leq n, m, S_i \leq 3 \times 10^5, m \leq \max \left\{S_i\right\}$。