4088. 仪式感

【题目背景】

“每一天都是一个新的日子，走运当然是好的，不过我情愿做到分毫不差，这样，运气来的时候，你就有所准备了”    ——《老人与海》by 海明威

【题目描述】

小 $L$ 喜欢仪式感。小 $F$ 喜欢集合。小 $L$   喜欢有仪式感的集合。

定义一个集合 $S$ 的 仪式感 为 $k$，当且仅当 $S$ 中的所有元素的最大公约数恰好为 $k$。

现在小 $F$ 有一个大小为 $n$ 的集合 $S$，小 $L$ 想请你对于 $∀$ $k ∈ [1, m]$，分别求出 $min{|S_0|}(S_0 ∈ A)$ 和 $max{|S_0|}(S_0 ∈ A)$，其中 $A$ 为 $S$ 的所有 仪式感 为 $k$ 的非空子集组成的集合。即意，分别求出最少/最多能从 $A$ 中取出多少个数，使它们的 $gcd = k$。

【输入格式】

第一行：两个正整数 $n$, $m$。

第二行：$n$ 个正整数 $S_{1∼n}$，表示小 $F$ 拥有的集合 $S$。

【输出格式】

输出共 $m$ 行。

对于 $∀ k ∈ [1, m]$，第 $k$ 行输出两个整数 $a, b$，其中 $a = min{|S_0|}，b = max{|S_0|}$。如果对于当前的 $k$，$A = ∅$，输出两个 $−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

【样例3】

点击下载样例3 

【数据规模与约定】

测试点 $1 \sim 2$：$n \leq 20$;

测试点 $3 \sim 4$：$n \leq 100， \sum S_i \leq 4 \times 10^4，m \leq 10$;

测试点 $5 \sim 6$：$n \leq 2000 ，m \leq 10$;

测试点 $7 \sim 10$：$n \leq 30,0000$;

对于所有数据，满足 $1 \leq n,m,S_i \leq 3 \times 10^5，m \leq max(S_i)$。