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