Когда Человек-Паук услышал, что в Баку много высоких зданий, он сразу же решил отправиться в Баку. Человек-Паук не в силах совладать с собой, когда увидел здесь высокие здания. Он начал перебегать от одного здания к другому и так без остановки прыгал.
В Баку имеется n зданий. Высота i-го здания равна h[i]
метров.
После длительного наблюдения за Человеком-Пауком вы увидели, что он может прыгнуть с i-го здания на j-е только в том случае, если остаток от деления h[i]
на h[j]
равно k.
Ваша задача — определить для каждого здания, на сколько других зданий Человек-Паук может прыгнуть прямо из этого здания.
В первой строке заданы два целых числа n (1 ≤ n ≤ 3 * 10^5
) и k (0 ≤ k ≤ 10^6
). В следующей строке заданы n целых чисел h[1]
, h[2]
, ..., h[n]
(1 ≤ h[i]
≤ 10^6
).
Выведите n целых чисел, разделенных пробелами, в одной строке. i-е из этих чисел должно быть равно количеству других зданий, с которых Человек-Паук может напрямую спрыгнуть с i-го здания.
В третьем тесте Вы можете прыгнуть со здания 1 на любое другое здание. Со здания 2 нельзя перепрыгнуть на любое другое здание. Вы можете прыгать только со здания 3 на здание 2. Вы можете прыгать только со здания 4 на здание 3. Вы можете прыгать с 5-го здания на 2-е и 4-е здания.