← 返回题目列表

Codeforces · 1967/C

C. 芬威克树

中文机器翻译题面 查看原题

让 $$$\operatorname{lowbit}(x)$$$ 表示 $$$x$$$ 的最低二进制位的值,例如$$$\operatorname{lowbit}(12)=4$$$,$$$\operatorname{lowbit}(8)=8$$$。

对于长度为 $$$n$$$ 的数组 $$$a$$$,如果长度为 $$$n$$$ 的数组 $$$s$$$ 满足 $$$s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353$$$ 对于所有$$$k$$$,那么$$$s$$$ 被称为$$$a$$$ 的芬威克树。我们将其表示为 $$$s=f(a)$$$。

对于正整数 $$$k$$$ 和数组 $$$a$$$,$$$f^k(a)$$$ 定义如下:

$$$$$$ f^k(a)= \begin{cases} f(a)&\textrm{if }k=1\\ f(f^{k-1}(a))&\textrm{否则。}\\ \end{cases} $$$$$$

给定一个长度为 $$$n$$$ 的数组 $$$b$$$ 和一个正整数 $$$k$$$。找到一个满足 $$$0\le a_i < 998\,244\,353$$$ 和 $$$f^k(a)=b$$$ 的数组 $$$a$$$。可以证明答案总是存在的。如果有多个可能的答案,您可以打印其中任何一个。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个正整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) 和 $$$k$$$ ($$$1\le k\le 10^9$$$),分别代表数组的长度和函数 $$$f$$$ 执行的次数。

每个测试用例的第二行包含一个数组 $$$b_1, b_2, \ldots, b_n$$$ ($$$0\le b_i < 998\,244\,353$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印一行,其中包含长度为 $$$n$$$ 的有效数组 $$$a$$$。

示例

输入 #1

2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16

输出 #1

1 1 1 1 1 1 1 1
1 2 3 4 5 6

注意

在第一个测试用例中,可以看出$$$f^1([1,1,1,1,1,1,1,1])=[1,2,1,4,1,2,1,8]$$$。

在第二个测试用例中,可以看出$$$f^2([1,2,3,4,5,6])=f^1([1,3,3,10,5,11])=[1,4,3,17,5,16]$$$。