원형 셀룰러 오토마톤

셀룰러 오토마톤은 정해진 형태의 격자 위에 놓인 셀들의 모임으로, 이웃한 셀들의 상태로부터 각 셀의 새로운 상태를 정하는 규칙에 따라 여러 번의 이산적인 시간 단계를 거치며 변화한다. 셀룰러 오토마톤의 차수(order) 는 그것이 가진 셀의 개수이며, 차수가 $n$ 인 오토마톤의 셀에는 $1$ 부터 $n$ 까지 번호를 매긴다.

셀의 차수 는 그 셀이 가질 수 있는 서로 다른 값의 개수이다. 차수가 $m$ 인 셀의 값은 $0$ 이상 $m-1$ 이하의 정수이다.

셀룰러 오토마톤의 가장 근본적인 성질 중 하나는 그것이 놓인 격자의 종류이다. 이 문제에서는 특별한 종류, 즉 셀의 차수가 $m$ 이고 차수가 $n$ 인 원형 셀룰러 오토마톤을 다룬다. 이를 $n,m$-오토마톤이라 부른다.

$n,m$-오토마톤에서 셀 $i$ 와 셀 $j$ 사이의 거리는 $\min(|i-j|,\; n-|i-j|)$ 로 정의한다. 어떤 셀의 $d$-이웃($d$-environment)이란 그 셀과의 거리가 $d$ 이하인 모든 셀의 집합이다.

매 $d$-스텝 마다 모든 셀의 값이 동시에 새 값으로 바뀐다. 셀 $i$ 의 새 값은 셀 $i$ 의 $d$-이웃에 속하는 셀들의 값의 합을 $m$ 으로 나눈 나머지이다.

$k$ 번의 $d$-스텝을 거친 뒤 $n,m$-오토마톤의 상태를 구하여라.

첫째 줄에 네 정수 $n$, $m$, $d$, $k$ 가 주어진다 ($1 \le n \le 500$, $1 \le m \le 1{,}000{,}000$, $0 \le d < n/2$, $1 \le k \le 10{,}000{,}000$). 둘째 줄에는 $0$ 이상 $m-1$ 이하의 정수 $n$ 개가 주어지며, 이는 오토마톤 셀들의 초기 값이다.

$k$ 번의 $d$-스텝을 거친 뒤 $n,m$-오토마톤의 각 셀의 값을 한 줄에 공백 하나로 구분하여 출력한다.