题目描述

Little Ivan likes to play Yamb and read Marvel superhero comics. His favorite superhero is spider-man, a friendly neighbourhood teenager named Peter Parker who got his superpowers via a radioactive spider bite. Ivan fantasizes that one day he will be able to jump from one skyscraper to another, just like spider-man does in the comics. During one such fantasy, he fell asleep.

In his dream he was no longer named Ivan, his name was Peter Parkour$^{1}$ and, you guessed it, he was able to use his parkour skills to jump between skyscrapers. He quickly realized that there are exactly $N$ skyscrapers in his surroundings and he somehow knew that $i$-th of those skyscrapers is $h_i$ meters tall. He knows that he is able to jump from the $i$-th skyscraper to the $j$-th skyscraper if the remainder when dividing $h_i$ with $h_j$ is equal to $K$. Help Ivan determine, for every skyscraper, the number of other skyscrapers he can jump to.

输入格式

The first line contains two integers $N$ ($1 \leq N \leq 300\,000$) and $K$ ($0 \leq K < 10^6$) from the task description.

The next line contains $N$ integers $h_i$ ($1 \leq h_i \leq 10^6$) from the task description.

输出格式

In a single line you should output $N$ space-separated integers such that the $i$-th of those integers represents the number of different skyscrapers on which Peter Parkour can jump on if he jumps from the $i$-th skyscraper.

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

提示

Clarification of the third example:

• From the first skyscraper of height 1 Peter can jump on any other skyscraper.
• From the second skyscraper of height 3 Peter can jump only on a skyscraper of height 2.
• From the third skyscraper of height 5 Peter can jump only on a skyscraper of height 2.
• From the fourth skyscraper of height 7 Peter can jump on skyscrapers of heights 2 and 3.
• From the fifth skyscraper of height 2 Peter cannot jump on any other skyscraper.

Scoring

• In test cases worth a total of $14$ points, it will hold $1 \leq N \leq 2\,000$
• In test cases worth an additional $14$ points, there will be at most $2\,000$ skyscrapers of different heights.
• In test cases worth an additional $14$ points, it will hold $K = 0$.