Description

小 Ivan 喜欢玩 Yamb 游戏，也喜欢阅读 Marvel 超级英雄漫画。他最喜欢的超级英雄是蜘蛛侠——那位因被放射性蜘蛛咬伤而获得超能力的邻家少年 Peter Parker。Ivan 总幻想有一天自己也能像漫画里的蜘蛛侠一样，在摩天大楼之间跳来跳去。在一次这样的幻想中，他睡着了。

在梦中，他不再叫 Ivan，而是叫 Peter Parkour$^{1}$，你猜对了，他能够利用自己的跑酷技巧在摩天大楼之间跳跃。他很快发现，周围正好有 $N$ 座摩天大楼，并且他莫名其妙地知道第 $i$ 座大楼的高度是 $h_i$ 米。他知道：如果 $h_i \bmod h_j = K$，他就可以从第 $i$ 座大楼跳到第 $j$ 座大楼。请你帮 Ivan 计算，对于每一座大楼，他能跳到多少其他大楼上。

$^{1}$：“Parkour”意为“跑酷”。

Input Format

第一行输入两个整数 $N$（$1 \leq N \leq 300\,000$）和 $K$（$0 \leq K < 10^6$）。

第二行输入 $N$ 个整数 $h_i$（$1 \leq h_i \leq 10^6$），表示每座大楼的高度。

Output Format

输出一行，包含 $N$ 个用空格分隔的整数，第 $i$ 个数表示 Peter Parkour 从第 $i$ 座大楼出发，可以跳到多少其他大楼上。

2 1
5 5

0 0

6 3
4 3 12 6 8 2

0 4 0 0 0 0

5 1
1 3 5 7 2

4 1 1 2 0

Hint

对第三个样例的说明：

• 从高度为 $1$ 的大楼出发，可以跳到任意其他大楼。
• 从高度为 $3$ 的大楼出发，只能跳到高度为 $2$ 的大楼。
• 从高度为 $5$ 的大楼出发，只能跳到高度为 $2$ 的大楼。
• 从高度为 $7$ 的大楼出发，可以跳到高度为 $2$ 和 $3$ 的大楼。
• 从高度为 $2$ 的大楼出发，无法跳到任何其他大楼。

评分说明

• 在价值 $14$ 分的测试点中，$1 \leq N \leq 2\,000$。
• 在额外 $14$ 分的测试点中，不同高度的大楼数量不超过 $2\,000$。
• 在额外 $14$ 分的测试点中，$K = 0$。

翻译由 ChatGPT-4.1 完成。