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 $$