上周，算法课的讲师布置了一项作业，要求确定给定伪代码函数的输出。尽管作业中只有一个问题，但讲师警告你不要低估它，并建议你多花点时间来完成。

你需要完成的作业内容如下：

给定一个长度为 $N$（下标从 $0$ 到 $N-1$）的正整数数组 $A[]$、一个整数 $K$ 以及以下伪代码函数。本题的任务是根据给定的输入确定该函数的输出。

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]

该函数的输出是什么（即 $B[0..N-1]$ 的值是多少）？请向助教询问输入 $A[]$、$N$ 和 $K$。

重要提示：由于 $B[0..N-1]$ 的返回值可能非常大，验证起来会很麻烦，因此你必须将 $B[0..N-1]$ 中的每个元素对 $998\,244\,353$ 取模。

由于题目看起来简短且容易，你决定将作业拖到提交截止日期前的最后一刻。你设法从助教那里拿到了所需的输入（数组 $A$、整数 $N$ 和整数 $K$），但在实现伪代码函数后，你很快就后悔了自己懒惰的决定。显然，直接实现该函数可能需要运行数小时。

现在你需要冷静下来，在截止日期前算出给定输入下该函数的输出。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$ ($1 \le N \le 100\,000; 1 \le K \le 10^9$)，分别表示输入数组 $A$ 的大小和给定的整数。下一行包含 $N$ 个整数 $A_i$ ($1 \le A_i < 998\,244\,353$)，表示数组 $A$ 的元素。

输出格式

输出一行 $N$ 个整数，每个整数之间用单个空格分隔，表示函数的输出（即数组 $B[]$）。将 $B[]$ 中的每个元素对 $998\,244\,353$ 取模。详见样例输出。

样例

样例输入 1

5 2
1 2 3 4 5

样例输出 1

24 120 60 40 30

样例输入 2

8 3
12 5 16 14 10 6 9 2

样例输出 2

14515200 14515200 14515200 14515200 14515200 14515200 14515200 14515200

样例输入 3

6 10
3 7 8 2 9 5

样例输出 3

56347321 169041963 833775940 811788154 844769833 639990479

样例输入 4

2 100
1 2

样例输出 4

917380677 917380677