Problem Description

Last week, your algorithm course's lecturer gave you an assignment to determine the output of a given pseudocode function. Even though the assignment contains only a single problem, the lecturer warned you not to underestimate it and suggests you spend more time doing it.

The following is the snapshot of the assignment that you need to finish before the deadline.

Given an array of positive integers $A[]$ of length $N$ (indexed from $0$ to $N-1$), an integer $K$, and the following pseudocode function. Your task in this problem is to determine the output of the following function from the given input.

SomeFunction(A[0..N-1], N, K):
    B[0..N-1] = A[0..N-1]
    for i = 0 to K-1:
        A[0..N-1] = B[0..N-1]
        for j = 0 to N-1:
            B[j] = A[j] × A[(j + 2^i) mod N]
    return B[0..N-1]

Here, 2^i means pow(2, i)

What is the output of the function (i.e. what are the values for $B[0..N-1]$)? Please ask your teaching assistant for the input $A[]$, $N$, and $K$.

IMPORTANT: As the return value for $B[0..N-1]$ can be very large, it can be very troublesome to verify, so you must modulo each element of $B[0..N-1]$ by $998244353$.

As the problem looks short and easy, you decided to leave the assignment to the last minute before the submission deadline. You managed to get the required input (the array $A$, integer $N$, and integer $K$) from the teaching assistant, but you quickly regret your lazy decision after implementing the function pseudocode. Apparently, a direct implementation of the function might need hours to run.

Now you need to calm down and figure out the output of the function given such input before the deadline.

Input Format

Input begins with two integers $N$ $K$ ($1 \leq N \leq 100\,000$; $1 \leq K \leq 10^9$) representing the size of input array $A$ and the given integer, respectively. The next line contains $N$ integers $A_i$ ($1 \leq A_i < 998\,244\,353$) representing the elements of array $A$.

Output Format

Output $N$ integers in a single line, each separated by a single space, representing the output of the function (i.e. the array $B[]$). Modulo each element in $B[]$ by $998\,244\,353$. See sample output for clarity.

5 2
1 2 3 4 5

24 120 60 40 30

8 3
12 5 16 14 10 6 9 2

14515200 14515200 14515200 14515200 14515200 14515200 14515200 14515200

6 10
3 7 8 2 9 5

56347321 169041963 833775940 811788154 844769833 639990479

2 100
1 2

917380677 917380677