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 (1 ≤ n ≤ 3 * 105) and k (0 ≤ k ≤ 106). The next line contains n integers h1, h2, ..., hn (1 ≤ hi ≤ 106).

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.