eolymp
Competitions

Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29

Spiderman in Baku

When Spider-Man heard that there are many tall buildings in Baku, he immediately decided to go to Baku. Spider-Man is unable to control himself when he sees the tall buildings here. He began to run from one building to another and jumped without stopping.

There are n buildings in Baku. The height of the i-th building is hi meters.

After watching Spider-Man for a long time, you saw that he can jump from the i-th building to the j-th building only if the remainder of dividing hi by hj equals to k.

Your task is to determine, for each building, how many other buildings Spider-Man can jump directly from this building.

Input

The first line contains two integers n (1n3 * 105) and k (0k106). The next line contains n integers h1, h2, ..., hn (1hi106).

Output

Print n integers on one line. The i-th of these numbers must be equal to the number of other buildings that Spider-Man can directly jump from the i-th building.

Explanation

In the third test, you can jump from building 1 to any other building. From building 2 you cannot jump to any other building. From building 3 you can only jump to building 2. From building 4 you can only jump to building 3. You can jump from the building 5 to the buildings 2 and 4.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 3
9 9
Output example #1
0 0
Input example #2
4 3
7 4 17 1
Output example #2
1 0 1 0
Input example #3
5 1
1 2 3 4 5
Output example #3
4 0 1 1 2
Source Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29