Фрирен анализирует барьер, возведенный Зерие над территорией проведения первого теста в экзамене на мага первого класса. Зерие — одна из древнейших и наиболее могущественных магов, поэтому разрушить этот барьер будет непросто. Но и Фрирен тоже имеет огромный тысячелетний опыт за плечами, поэтому сразу поняла, что барьер параметризован $$$n$$$ целыми числами $$$a_i$$$.
Для того, чтобы разрушить барьер, Фрирен необходимо по этим $$$a_i$$$ найти ключевую последовательность этого барьера. Ключевая последовательность состоит ровно из $$$k$$$ целых чисел $$$b_i$$$, где $$$$$$b_i = \mathtt{mex}\left( \left\lfloor\frac{a_1}{i}\right\rfloor, \left\lfloor\frac{a_2}{i}\right\rfloor, \ldots, \left\lfloor\frac{a_n}{i}\right\rfloor \right) \text{.}$$$$$$
Здесь $$$\mathtt{mex}$$$ означает минимальное целое неотрицательное число, которое отсутствует в последовательности, а $$$\left\lfloor\frac{a_j}{i}\right\rfloor$$$ — неполное частное при делении $$$a_j$$$ на $$$i$$$. Например, при $$$i = 3$$$ и $$$a = [1, 2, 5, 6, 13, 23]$$$, после деления на $$$i$$$ мы получим последовательность $$$[0, 0, 1, 2, 4, 7]$$$, и $$$\mathtt{mex}(0, 0, 1, 2, 4, 7) = 3$$$.
Иными словами, требуется для каждого $$$i$$$ от $$$1$$$ до $$$k$$$ найти $$$\mathtt{mex}$$$ последовательности, образованной из $$$a$$$ делением нацело на $$$i$$$. Помогите Фрирен найти ключевую последовательность барьера, чтобы она могла его разрушить и помочь своим сокомандникам.
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ — длина последовательности $$$a$$$ и длина искомой ключевой последовательности ($$$1 \le n, k \le 10^6$$$).
Во второй строке ввода через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы последовательности параметров барьера ($$$0 \le a_i \le 10^6$$$).
В единственной строке ввода через пробел выведите $$$k$$$ целых чисел — элементы ключевой последовательности барьера.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
1 | 12 | $$$n, k \le 100$$$ | полная | |
2 | 13 | $$$a_i \le 10$$$ для всех $$$i$$$ | первая ошибка | |
3 | 13 | $$$n \le 10$$$ | первая ошибка | |
4 | 12 | $$$n, k \le 1000$$$ | 1 | первая ошибка |
5 | 21 | $$$n, k \le 10^5$$$ | 1, 4 | первая ошибка |
6 | 29 | без дополнительных ограничений | 1 – 5 | первая ошибка |
6 51 5 23 6 13 2
0 4 3 2 3
10 105 9 8 13 25 7 11 6 45 10
0 0 0 0 0 3 2 2 3 3