Given a polynomial $F(z) = \sum_{i=0}^{n-1} f_iz^i$ and $m$ non-negative integers $x_1, x_2, \dots, x_m$, you need to calculate the value of $F(x_i)$ for each $1 \leq i \leq m$.
Input
The first line contains two integers $n$ and $m$, representing the degree of the polynomial as $n-1$ and the number of queries, respectively.
The next line contains $n$ integers $f_0, f_1, \dots, f_{n-1}$.
The next $m$ lines each contain an integer $x_i$, representing a query.
Output
Output $m$ lines, each containing an integer representing the result of the query modulo $998,244,353$.
Examples
Input 1
6 6
1 1 4 5 1 4
1
19
191
1919
810
1919810Output 1
16
10070476
934460929
474354141
579687411
895765304Subtasks
For all data, $1 \leq n, m \leq 10^6$.
| Test Case | $n, m$ |
|---|---|
| 1 | $100$ |
| 2 | $5 \times 10^3$ |
| 3 | $3 \times 10^4$ |
| 4 | $10^5$ |
| 5 | $10^6$ |