시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 88 21 18 23.077%

문제

원래 곰은 밥을 먹을 때 식탁에 앉아서 먹지 않는다. 그런데, 요즘에는 의자에 앉아서 밥을 먹는 곰이 일부 있다고 한다.

강호는 곰을 위한 거대한 레스토랑의 웨이터이다. 이 레스토랑은 무한 개의 의자를 가지고 있고, 한 줄로 놓여져 있다. 의자는 입구에서 가까운 것부터 1번, 2번, ... 으로 번호가 매겨져 있다.

곰은 매우 크기 때문에, 붙어서 앉을 수 없다. 두 곰이 의자에 앉았을 때, 두 곰이 앉은 의자의 번호의 차이는 d보다 크거나 같아야 한다.

예를 들어, d=10인 경우에, 두 곰이 47번과 57번 의자에 앉을 수는 있지만, 47번과 56번 의자에 앉을 수는 없다.

레스토랑은 방금 문을 열었고, 모든 의자는 비어있다.

오늘은 총 N명의 곰이 레스토랑을 방문할 것이고, 한 번에 곰 한마리씩 도착한다. 곰은 레스토랑이 문을 닫을 때까지 의자에서 일어나지 않는다.

레스토랑을 방문하는 곰은 각자 원하는 자리가 있다. i번째 곰이 원하는 자리를 A[i]라고 했을 때, 그 곰의 자리는 A[i]보다 크거나 같아야 한다.

곰을 자리로 안내할 때, 강호는 곰이 앉을 수 있는 의자 중에서 번호가 가장 작은 것을 선택하려고 한다.

곰이 원하는 자리가 도착하는 순서대로 주어졌을 때, 각각의 곰이 어디에 앉는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 곰의 수 N과 d가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ d ≤ 106)

둘째 줄에는 곰이 원하는 자리가 도착하는 순서대로 주어진다. 곰이 원하는 자리는 1보다 크거나 같고, 106보다 작거나 같은 자연수이다.

출력

곰이 도착하는 순서대로 앉는 자리를 공백으로 구분해 출력한다.

예제 입력 1

4 10
1 21 11 7

예제 출력 1

1 21 11 31

예제 입력 2

4 11
1 21 11 7

예제 출력 2

1 21 32 43

예제 입력 3

4 1000000
1000000 1000000 1000000 1

예제 출력 3

1000000 2000000 3000000 4000000

예제 입력 4

4 999999
1000000 1000000 1000000 1

예제 출력 4

1000000 1999999 2999998 1

출처