MPOLEVAL - Polynomial Evaluation - Angry Teacher

no tags 

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mpoleval


Mr. O'Cruel bắt Andrew tính giá trị một đa thức dạng khủng như sau vì tội lười học.

Cho đa thức p(x) = anxn + an-1xn-1 + . . . + a1x + a0 với hệ số nguyên :

Andrew cần tính giá trị của đa thức tại k số nguyên liên tiếp bắt đầu từ l. Sau đó, với mỗi giá trị x từ l đến l + k - 1, Andrew phải tính tổng bình phương m chữ số của cùng của p(x). Giúp him. :)


Teacher of the month.

Input

Dòng đầu gồm các số nguyên n, l, k, và m (0 <= n <= 10, 0 <= l <= 10^1000 , 1 <= k <= 1000, 1 <= m <= 1000).

Sau đó là n+1 dòng chứa các hệ số của đa thức : an , an-1 , . . . , a1 , a0 (0 <= ai <= 10^1000).


SAMPLE INPUT
3 0 10 2
1
0
2
1

Output

Ghi ra k dòng cho mỗi x từ l tới l + k - 1, mỗi dòng là tổng bình phương m chữ số cuối cùng của p(x).


SAMPLE OUTPUT
1
16
10
25
58
45
85
89
85
80



Added by:psetter
Date:2009-02-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Resource:Northeastern Europe 2004 Northern Subregion