Spiderman

꼬마 Ivan은 Yamb 놀이와 마블 슈퍼히어로 만화 읽기를 좋아한다. 그의 최애 히어로는 방사능 거미에 물려 초능력을 얻은 동네 청소년 Peter Parker, 즉 spider-man이다. Ivan은 언젠가 만화 속 spider-man처럼 마천루에서 마천루로 뛰어넘을 수 있기를 상상한다. 그러던 어느 날 그는 잠이 들었다.

꿈속에서 그는 더 이상 Ivan이 아니라 Peter Parkour였고, 짐작했겠지만 파쿠르1 실력으로 마천루 사이를 뛰어넘을 수 있었다. 그는 주변에 마천루가 정확히 N채 있고, i번째 마천루의 높이가 hi미터라는 것을 어째서인지 알고 있었다. i번째 마천루에서 j번째 마천루로 뛰어넘을 수 있는 조건은 hi를 hj로 나눈 나머지가 K와 같은 것이다. Ivan이 각 마천루마다 뛰어넘을 수 있는 다른 마천루의 수를 구하도록 도와주자.

1 2004년의 인터넷 센세이션. 본드 영화에도 나왔으며, 목표는 A지점에서 B지점까지 최대한 창의적으로 이동하는 것이다.

첫째 줄에 문제 설명에 나온 두 정수 N (1 ≤ N ≤ 300 000)과 K (0 ≤ K < 106)가 주어진다.

다음 줄에 문제 설명에 나온 N개의 정수 hi (1 ≤ hi ≤ 106)가 주어진다.

한 줄에 N개의 정수를 공백으로 구분해 출력한다. i번째 정수는 i번째 마천루에서 뛰어넘을 때 Peter Parkour가 이동할 수 있는 서로 다른 마천루의 수이다.

세 번째 예제의 해설:

• 높이 1인 첫 번째 마천루에서는 Peter가 다른 모든 마천루로 뛰어넘을 수 있다.
• 높이 3인 두 번째 마천루에서는 높이 2인 마천루로만 뛰어넘을 수 있다.
• 높이 5인 세 번째 마천루에서는 높이 2인 마천루로만 뛰어넘을 수 있다.
• 높이 7인 네 번째 마천루에서는 높이 2와 3인 마천루로 뛰어넘을 수 있다.
• 높이 2인 다섯 번째 마천루에서는 다른 어떤 마천루로도 뛰어넘을 수 없다.