問題文

$p = 1009$ とする。
入力によって与えられた $0$ 以上 $p$ 未満の整数 $K_0, K_1, \cdots, K_M$ について、$K := \sum_{j=0}^M K_j p^j$とおく。
入力によって与えられた非負整数 $A_{1,0}, \cdots, A_{1,N}$ に対して、$A_{k, 0}, \cdots, A_{k, N}$ を以下の操作によって帰納的に定める :

$A_{k+1, n} := \sum_{i = 0}^{n} A_{k, i}A_{1, n-i}$

このとき、$A_{K, 0}, \cdots, A_{K, N}$ を $p$ で割った余りを順に出力せよ。

入力

$M \ N$
$K_0 \ \cdots \ K_M$
$A_{1, 0} \ \cdots \ A_{1, N}$

$0 \leq M < 4 \times 10^5,$
$0 \leq N < 2 \times 10^3,$
$0 \leq K_m < p \ (m = 0, \cdots, M, \ K_M \neq 0),$
$0 \leq A_{1, n} < p \ (n = 0, \cdots, N),$

出力

$A_{K, 0}, \cdots, A_{K, N}$ を $p$ で割った余りを順に出力せよ。半角スペース一個で区切ること。

サンプル

0 0
1
789

789

0 3
3
1 1008 0 0

1 1006 3 1008

1 5
99 100
1 2 3 4 5 6

1 198 530 691 669 390