Spiderman

Time limit2sMemory limit512 MB

Summary

For each skyscraper height, count how many other buildings it can jump to, where a jump from h_i to h_j is allowed only when h_i mod h_j equals K.

Level: Medium7 of 10
Topics: Math, Number theory, Array, Brute force
Solved: No attempts yet

Problem

Little Ivan likes to play Yamb and read Marvel superhero comics. His favorite superhero is spider-man, a friendly neighborhood teenager named Peter Parker who got his superpowers from 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 could use his parkour1 skills to jump between skyscrapers. He quickly realized that there are exactly N skyscrapers in his surroundings, and he somehow knew that the i-th of those skyscrapers is hi meters tall. He knows that he can jump from the i-th skyscraper to the j-th skyscraper if the remainder when dividing hi by hj equals K. Help Ivan determine, for every skyscraper, the number of other skyscrapers he can jump to.

1Internet sensation of 2004. It was in the Bond films; the goal is to get from point A to point B as creatively as possible.

Input

The first line contains two integers N (1 ≤ N ≤ 300 000) and K (0 ≤ K < 106) from the task description.

The next line contains N integers hi (1 ≤ hi ≤ 106) 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 if he jumps from the i-th skyscraper.

Hint

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.

Examples3

Example 1
Input
```
2 1
5 5
```
Expected output
```
0 0
```
Example 2
Input
```
6 3
4 3 12 6 8 2
```
Expected output
```
0 4 0 0 0 0
```
Example 3
Input
```
5 1
1 3 5 7 2
```
Expected output
```
4 1 1 2 0
```