You are given an array $A$ of integers of size $N$ , and one more integer $K$. Now, we define $K$ distinct functions, $f_i(l,r), 1 \le i \le K$. All functions have the domain equal to the set of all ordered pairs of integers $\{ (x,y) : \hspace{0.2cm} x \le y$ and $1 \le x,y \le N \}$

$f_i(l,r) =( \sum_{j=l}^{r} a[j] )^{i}$.

Now you need to find and print for for each of the $K$ functions, the sum of function values of all elements in its domain. As the answer could be rather large, you need to find and print it Modulo $998244353$, a widely used prime.

Input Format :

The first line contains $2$ space separated integers $N$ and $K$. The next line contains $N$ space separated integers, denoting the given array.

Output Format:

Print $K$ space separated integers, where the $i^{th}$ integer is the answer for the $i^{th}$ function described above.

Constraints :

$1 \le N \cdot K \le 2 \cdot 10^6$

$1 \le N,K \le 10^6$, this ensures the input/output size remains resonable.

$0 \le A[i] <  998244353$