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) = a_nx^n + a_{n - 1}x^{n - 1} + \dots + a_1x + a_0~ 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ố cuối 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 \le n \le 10~, ~0 \le l \le 10^{1000}~, ~1 \le k \le 1000~, ~1 \le m \le 1000)~.

Sau đó là ~n + 1~ dòng chứa các hệ số của đa thức: ~a_n, a_{n- 1}, \dots, a_1, a_0~ ~(0 \le a_i \le 10^{1000})~.

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 Input

3 0 10 2
1
0
2
1

Sample Output

1
16
10
25
58
45
85
89
85
80