rail   1년 전

문제

한 나라에는 N개의 도시가 있고, 이 도시는 일직선 위에 위치해 있다. 각 도시는 s_i​개의 관광지를 가지고 있다.

관광객들이 한 도시의 관광지뿐 아니라 다른 도시의 관광지도 즐길 수 있도록, X-tensive 회사는 각 도시에 망원경을 설치하기로 했다.

그러나 한 도시에서 관광객들이 볼 수 있는 관광지의 수가 R개를 초과하면, 다른 도시에 방문할 필요가 없어지므로 안 된다.

이를 위해 각 망원경의 세기를 조절할 수 있다.

  • 세기 <0> → 관광객은 해당 도시의 관광지만 볼 수 있다.

  • 세기 <1> → 관광객은 인접한 도시들의 관광지도 함께 볼 수 있다.

  • 세기 <2> → 관광객은 그 이웃의 이웃 도시까지 볼 수 있고, 이런 식으로 확장된다.

물론, 망원경의 세기가 너무 커서 나라의 경계를 넘어서는 경우는 허용되지 않는다.

X-tensive 회사는 충분히 논의한 끝에, 각 망원경을 가능한 최대 세기로 설정하되 모든 조건을 만족시키기로 했다.

여러분의 임무는 각 도시의 망원경 세기를 결정하거나, 불가능하다면 -1을 출력하는 것이다.

입력

  • 첫 번째 줄에는 두 정수 N과 R이 주어진다.

    • N: 나라의 도시 개수

    • R: 한 도시에서 볼 수 있는 관광지의 최대 개수

    • (3≤N≤10^5, 1≤R≤10^14)

  • 두 번째 줄에는 N개의 정수 s_i​가 공백으로 구분되어 주어진다.

    • s_i​​: 각 도시에 있는 관광지의 개수

    • (1≤s_i≤10^9)


출력

총 N줄을 출력한다.

  • i번째 줄에는 i번째 도시의 망원경 세기를 출력한다.

  • 조건을 만족하는 세기를 설정할 수 없는 경우 -1을 출력한다.

댓글을 작성하려면 로그인해야 합니다.