Stocks Trading

Problem Description

小笋正在炒股赚钱，初始时小笋有 $0$ 块钱。 在接下来的 $n$ 天里，第 $i$ 天小笋有 $p_{i,j}$ 的概率获得 $j$ 的收益（若 $j<0$，则表示亏损 $-j$ 块钱）。保证 $\vert j\vert \le m$。 小笋想知道，对于每个 $1\le i\le n$，他在第 $i$ 天之后仍未破产的概率，答案对 $998\,244\,353$ 取模。 对于一个整数 $1\le i\le n$，我们认为第 $i$ 天之后仍未破产，当且仅当在第 $1,\dots,i$ 天后，小笋获得的收益总和都是非负的。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 5$）表示数据组数。对于每组测试数据： 第一行输入两个整数 $n,m$（$1\le n\cdot m\le 2\cdot 10^5$），表示炒股的天数和盈亏变化上限。 接下来 $n$ 行，每行输入 $2m+1$ 个整数，表示 $p_{i,-m},\ldots,p_{i,0},\ldots,p_{i,m}$，保证 $0\le p_{i,j}<998\,244\,353$，$\sum_{j=-m}^m p_{i,j}\equiv 1\pmod{998\,244\,353}$。 保证 $\sum n\cdot m\le 5\cdot 10^5$。

Output

对于每组测试数据，输出一行 $n$ 个整数，表示他在第 $i$ 天之后仍未破产的概率对 $998\,244\,353$ 取模后的结果。

Sample Input

2
2 1
686548415 824884764 485055528
865229185 425862472 705397050
4 3
226456437 781657634 953505677 786990797 979939602 36102152 228325114
217435438 895821742 147562948 758530679 117446701 209845760 648089792
629966894 667076671 794603759 146615929 154508086 681936529 918269545
50011395 395474405 661692228 728427341 576707884 43321994 539097813

Sample Output

311695939 991437870
34868959 43278718 71584961 671423019

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（10）