고고학자인 당신은 고대 유적을 연구하다가 마법의 검 $n$자루를 발견하였습니다. 모든 검을 조사한 결과 당신은 다음과 같은 사실을 알아냈습니다.
* 최초의 검은 단 한 자루가 있었습니다.
* 이후 고대인들은 다른 검을 복제하는 방식으로 검을 추가로 만들었습니다.
* 검을 복제할 때마다 검에 깃든 마법의 힘이 줄어듭니다. 그래서 한 검은 최대 두 번만 복제할 수 있었습니다.
* 검이 만들어진 시점부터 $k$년 이내에는 검을 복제할 수 없었습니다.
당신은 검 $n$자루가 언제 만들어졌는지를 알고 있고, 그 정보로부터 각 검의 원본이 어느 검인지를 추정해보고 싶습니다. 여러 가지 경우가 가능할 수도 있지만 하나만 찾으면 됩니다.
<입력>
첫째 줄에 문제에 언급된 두 개의 정수 $n\;(1\le n\le 100\;000)$, $k\;(1\le k\le 10^8)$가 주어집니다.둘째 줄에 $n$개의 정수 $a_1,\;a_2,\;...\;a_n$이 주어집니다. $a_i$는 $i$번째 검이 몇 년 전에 만들어졌는지를 나타내며, $0\le a_i\le 10^9$입니다.
<출력> 만약 당신이 알아낸 사실과 모순이 생긴다면 $-1$을 출력합니다.
그렇지 않다면 한 줄에 $n$개의 정수를 공백으로 구분하여 출력합니다.
$i$번째 정수는 $i$번째 검이 몇 번째 검의 복사본인지 나타내야 합니다. 단, 최초에 존재했던 검에 대해서는 `0`을 출력하면 됩니다.
iktk 2년 전 2
<문제>
고고학자인 당신은 고대 유적을 연구하다가 마법의 검 $n$자루를 발견하였습니다. 모든 검을 조사한 결과 당신은 다음과 같은 사실을 알아냈습니다.
* 최초의 검은 단 한 자루가 있었습니다.
* 이후 고대인들은 다른 검을 복제하는 방식으로 검을 추가로 만들었습니다.
* 검을 복제할 때마다 검에 깃든 마법의 힘이 줄어듭니다. 그래서 한 검은 최대 두 번만 복제할 수 있었습니다.
* 검이 만들어진 시점부터 $k$년 이내에는 검을 복제할 수 없었습니다.
당신은 검 $n$자루가 언제 만들어졌는지를 알고 있고, 그 정보로부터 각 검의 원본이 어느 검인지를 추정해보고 싶습니다. 여러 가지 경우가 가능할 수도 있지만 하나만 찾으면 됩니다.
<입력>
첫째 줄에 문제에 언급된 두 개의 정수 $n\;(1\le n\le 100\;000)$, $k\;(1\le k\le 10^8)$가 주어집니다.둘째 줄에 $n$개의 정수 $a_1,\;a_2,\;...\;a_n$이 주어집니다. $a_i$는 $i$번째 검이 몇 년 전에 만들어졌는지를 나타내며, $0\le a_i\le 10^9$입니다.
<출력>
만약 당신이 알아낸 사실과 모순이 생긴다면 $-1$을 출력합니다.
그렇지 않다면 한 줄에 $n$개의 정수를 공백으로 구분하여 출력합니다.
$i$번째 정수는 $i$번째 검이 몇 번째 검의 복사본인지 나타내야 합니다. 단, 최초에 존재했던 검에 대해서는 `0`을 출력하면 됩니다.