화난 선생님

오크루엘(O'Cruel) 선생님은 9학년 학생들에게 수학을 가르친다. 학생들은 대개 게을러서 숙제하기를 싫어하고, 반대로 선생님은 게으른 학생을 싫어한다.

앤드루(Andrew)가 또 숙제를 해 오지 않아 특별 과제를 받았다. 이 과제를 끝내지 못하면 그는 학교에서 쫓겨난다. 과제 자체는 쉬워 보이지만 계산이 매우 번거로워 시간이 오래 걸린다.

앤드루에게는 정수 계수를 가진 다항식 $p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ 이 주어진다. 그는 $l$부터 시작하는 연속한 정수 $k$개 각각에 대해 이 다항식의 값을 계산해야 한다. 그런데 그 값을 모두 적으면 종이가 너무 많이 필요하므로, 과제를 끝냈다는 증거로 $l$부터 $l + k - 1$까지의 각 $x$에 대해 $p(x)$를 십진법으로 나타냈을 때 마지막 $m$개 자리 숫자의 제곱의 합을 제출해야 한다.

$p(x)$의 자릿수가 $m$보다 적으면, 부족한 상위 자리는 $0$으로 채워진 것으로 본다(제곱이 $0$이므로 합에는 영향을 주지 않는다).

앤드루는 게을러서 직접 하고 싶어 하지 않으니, 대신 요청된 값을 계산하는 프로그램을 작성하라.

첫째 줄에 $n$, $l$, $k$, $m$이 주어진다 ($0 \le n \le 10$, $0 \le l \le 10^{1000}$, $1 \le k \le 1000$, $1 \le m \le 1000$).

이어지는 $n + 1$개의 줄에 다항식의 계수 $a_n, a_{n-1}, \ldots, a_1, a_0$이 순서대로 한 줄에 하나씩 주어진다 ($0 \le a_i \le 10^{1000}$).

$k$개의 줄을 출력한다. $x$가 $l$부터 $l + k - 1$까지 변할 때, 각 줄에 $p(x)$의 마지막 $m$개 자리 숫자의 제곱의 합을 출력한다.