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 h[i] 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 h[i] by h[j] 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 (1 ≤ n ≤ 3 * 10^5) and k (0 ≤ k ≤ 10^6). The next line contains n integers h[1], h[2], ..., h[n] (1 ≤ h[i] ≤ 10^6).

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.

Examples

Note

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.