Problem Description

There is an $m$-term polynomial $p(x)$ and two parameters $c$ and $t$, where $p(x)=a_0+a_1x+\dots+a_{m-1}x^{m-1}$.
Define a new function $s(n)$:

Please compute $s(c),s(c^2),\dots,s(c^t)$.

Input Format

The first line contains three positive integers $m,c,t$.
The second line contains $m$ positive integers $a_0,a_1,\dots,a_{m-1}$.

Output Format

Output $t$ lines. The $i$-th line contains one positive integer $s(c^i)$.

8 10 4
3 1 4 1 5 9 2 6

35683652
171899188
780914481
858211065

Hint

For $10\%$ of the testdata, $t\le2,c\le100$.
For $30\%$ of the testdata, $t\le1000,m\le1000$.
For $50\%$ of the testdata, $t\le5\cdot10^4,m\le5\cdot10^4,c\le10^{12}$.
For another $10\%$ of the testdata, $c=123456789$.
For all testdata, $1\le t\le2\cdot10^5,1\le m\le2\cdot10^5,1\le c\le10^{18}$.

Translated by ChatGPT 5