COCI '19 Contest 4 #2 Spiderman

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

Input

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

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

Output

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.

Scoring

In test cases worth a total of 14 points, it will hold 1 \le N \le 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.

Sample Input 1

2 1
5 5

Sample Output 1

0 0

Sample Input 2

6 3
4 3 12 6 8 2

Sample Output 2

0 4 0 0 0 0

Sample Input 3

5 1
1 3 5 7 2

Sample Output 3

4 1 1 2 0

Explanation for Sample Output 3

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.


Comments

There are no comments at the moment.