Huah 有 $n + k$ 座城市，编号为 $1, 2, \dots, n + k$。对于城市 $i$ ($1 \le i < n + k$) 到城市 $i + 1$，有 $n + k - i$ 条不同的单向道路。

对于每个 $x = 1, 2, \dots, n - 1$，从城市 $i$ ($x < i \le n + k$) 到城市 $i - x$ 有 $a_x$ 条不同的单向道路。

对于 $m = k + 1, k + 2, \dots, k + n$，求从城市 $k + 1$ 到城市 $m$ 且恰好经过 $k$ 条道路的路径数量。

当且仅当两条路径所经过的边序列不同时，它们被视为不同的路径。答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 14$)，表示测试用例的数量。每个测试用例：

第一行输入两个整数 $n, k$ ($2 \le n \le 2 \times 10^5, 1 \le k \le 2 \times 10^5$)。

第二行输入 $n - 1$ 个整数 $a_1, a_2, \dots, a_{n-1}$ ($0 \le a_i \le 998244352$)。

在第 $i$ ($1 \le i < T$) 个测试用例和第 $i + 1$ 个测试用例之间有一个空行。

输入保证 $\sum (n + k) \le 1006769$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数，其中第 $i$ 个整数表示当 $m = k + i$ 时的答案。

样例

输入 1

4
3 2
1 2
3 1
1 2
5 10
2 3 3 3
3 3
166374059 748683265

输出 1

5 0 2
0 2 0
114307026 825469567 425461680 73846080 5140800
5 2 0