MPOLEVAL - Polynomial Evaluation - Angry Teacher

Giới hạn

• Thời gian: 0.629s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

 

---

• Người up: vdmedragon
• Nguồn bài: Northeastern Europe 2004 Northern Subregion