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

对于一个长度为 $n$ 的数组 $a$，如果一个长度为 $n$ 的数组 $s$ 满足对于所有的 $k$，都有 $s_k = \left( \sum_{i=k-\text{lowbit}(k)+1}^{k} a_i \right) \bmod 998\,244\,353$，则称 $s$ 是 $a$ 的树状数组。我们将其记作 $s = f(a)$。

对于一个正整数 $k$ 和一个数组 $a$，$f^k(a)$ 的定义如下：

$$f^k(a) = \begin{cases} f(a) & \text{if } k = 1 \\ f(f^{k-1}(a)) & \text{otherwise.} \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 \le n \le 2 \cdot 10^5$) 和 $k$ ($1 \le k \le 10^9$)，分别表示数组的长度和函数 $f$ 的执行次数。

每个测试用例的第二行包含一个数组 $b_1, b_2, \dots, 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]$。