Angry Teacher

Mr. O'Cruel teaches Math to ninth-grade students. Students are usually lazy and dislike doing their homework, and Mr. O'Cruel dislikes lazy students.

Andrew failed to do his homework again, so he was given a special task. If he does not finish it, he will be expelled from school. The task looks easy, but it is very tedious and takes a lot of time.

Andrew is given a polynomial $p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ with integer coefficients. He must evaluate the polynomial for $k$ consecutive integers starting from $l$. Writing down all of these values would take far too much paper, so as proof that he completed the task, for each $x$ from $l$ to $l + k - 1$ Andrew must report the sum of the squares of the last $m$ digits of $p(x)$ in decimal notation.

If $p(x)$ has fewer than $m$ digits, treat the missing higher-order digits as zeros (their squares add nothing to the sum).

Since Andrew is lazy and does not want to do this himself, write the program that computes the requested values for him.

The first line contains $n$, $l$, $k$, and $m$ ($0 \le n \le 10$, $0 \le l \le 10^{1000}$, $1 \le k \le 1000$, $1 \le m \le 1000$).

The next $n + 1$ lines contain the coefficients of the polynomial $a_n, a_{n-1}, \ldots, a_1, a_0$, one per line ($0 \le a_i \le 10^{1000}$).

Output $k$ lines. For $x$ from $l$ to $l + k - 1$, output the sum of the squares of the last $m$ digits of $p(x)$.