P13423 [COCI 2019/2020 #4] Spiderman

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.

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$.