量规

时间限制：$2.0\text{ s}$

空间限制：$128\text{ MiB}$

题目描述

一条精密零件生产线会加工多种规格的环形分度盘。一个规格为 $a$ 的分度盘沿圆周均匀分布了 $a$ 个刻度。工厂使用带有 $d$ 个等距触点的环形量规进行快速检查。

当且仅当 $d$ 整除 $a$ 时，转动量规后可以使所有触点同时落在分度盘的刻度上。此时称这只量规适用于该分度盘。量规的触点数 $d$ 为正整数。

生产线按顺序送来 $n$ 个分度盘，第 $i$ 个分度盘的刻度数为 $a_i$。质检人员需要在任意时刻选择同一只量规，对已经送达的分度盘中至少 $k$ 个进行统一抽检。因此，若某个正整数 $d$ 是当前至少 $k$ 个 $a_j$ 的约数，就称对应的量规当前可用。

触点越多，单次检查能观测的位置越多。在每个分度盘送达后，请求出触点数最大的当前可用量规，也就是至少 $k$ 个已到达数值的公约数中的最大值。若当前总共还不足 $k$ 个分度盘，输出 $0$。

输入格式

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

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，按送达顺序给出每个分度盘的刻度数。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示前 $i$ 个分度盘送达后，触点数最多的可用量规；不存在时输出 $0$。

输入样例 1

5 2
6 10 15 9 30

输出样例 1

0 2 5 5 15

输入样例 2

6 3
8 4 16 6 12 24

输出样例 2

0 0 4 4 4 8

输入样例 3

见附件 sample/gauge3.in

输出样例 3

见附件 sample/gauge3.out

数据范围

对于所有测试点，保证 $1\le k\le n\le 2\times 10^5$，$1\le a_i\le 10^6$。

每个测试点单独计分。