题目描述

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

以下是你需要在截止日期前完成的作业内容。

给定一个长度为 $N$ 的正整数数组 $A[]$（下标从 $0$ 到 $N-1$），一个整数 $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]

这里，2^i 表示 pow(2, i)

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

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

由于这个问题看起来简短且简单，你决定将作业留到提交截止前的最后一刻。你成功从助教那里获得了所需的输入（数组 $A$、整数 $N$ 和整数 $K$），但在实现伪代码函数后，你很快为自己的懒惰决定感到后悔。显然，直接实现该函数可能需要数小时才能运行。

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

输入格式

输入以两个整数 $N$ $K$（$1 \leq N \leq 100\,000$；$1 \leq K \leq 10^9$）开始，分别表示输入数组 $A$ 的大小和给定的整数。接下来一行包含 $N$ 个整数 $A_i$（$1 \leq A_i < 998\,244\,353$），表示数组 $A$ 的元素。

输出格式

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

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