시원하게 유지하기

학기 과제가 몰리면서 연구실 냉장고에 음료수를 다시 채워야 합니다. 냉장고에는 $s$개의 칸이 있고, 각 칸에는 음료수를 $d$병까지 넣을 수 있습니다. 새로 넣을 음료수는 $n$병입니다. 냉장고에 이미 있는 음료수는 시원하지만, 새 음료수는 시원하지 않습니다. 마시기 좋은 온도가 되려면 냉장고에서 한동안 식혀야 합니다.

냉장고는 앞쪽에서만 채울 수 있습니다. 이상적인 상황이라면 지금 들어 있는 음료수를 모두 꺼낸 뒤 새 $n$병을 넣고, 그다음에 시원한 예전 음료수를 새 음료수 앞에 둘 것입니다. 하지만 시험 두 개와 과제 마감이 다가와서 그렇게 할 시간이 없습니다.

그래서 새 음료수를 냉장고 앞쪽에 넣고 잘 되기를 바랄 것입니다. 다만 새 음료수를 어느 칸에 넣을지는 신중하게 고를 수 있습니다. 학생이 음료수를 가져갈 때마다, 비어 있지 않은 칸 중에서 균등한 확률로 무작위로 고른 칸의 앞쪽에서 한 병을 가져갑니다. 다음 $m$명의 학생이 모두 시원한 음료수를 받을 확률이 최대가 되도록 새 음료수를 어디에 넣을지 정하세요.

첫 번째 줄에 정수 네 개 $n$, $m$, $s$, $d$가 주어집니다($1 \le n, m, s, d \le 100$). 각각 새 음료수의 개수, 최적화 대상이 되는 학생 수, 칸의 개수, 칸마다의 용량입니다. 두 번째 줄에는 정수 $s$개 $c_1, \ldots, c_s$가 주어집니다($0 \le c_i \le d$). $c_i$는 현재 $i$번째 칸에 들어 있는 음료수의 개수입니다.

냉장고에 새 $n$병을 모두 넣을 빈 공간이 있다고 가정해도 됩니다.

다음 $m$명의 학생이 모두 시원한 음료수를 받을 가능성이 있으면, 그 확률을 최대로 만드는 $n$병의 補충 방법을 나타내는 정수 $s$개를 출력합니다. $i$번째 정수는 $i$번째 칸의 앞쪽에 넣는 새 음료수의 개수입니다. 최적의 방법이 여러 개면 그중 아무거나 출력해도 됩니다. 다음 $m$명의 학생이 모두 시원한 음료수를 받는 것이 불가능하면 "impossible"을 출력합니다.