【MX-S3-T4】「FeOI Round 1」醒餞の鳥 (feat. Feryquitous)


有 $n$ 个学生（编号为 $1 \sim n$）参加了一场有 $m$ 门学科（编号为 $1 \sim m$）的考试，现在你知道，学生 $i$ 的第 $j$ 门学科考试的成绩为 $a_{i, j}$。 现在你想要给这些学生排名。由于成绩不形成偏序关系的两个学生实力难以比较，所以你打算设置 $m$ 个实数 $p_{1 \sim m}$（要求满足 $\sum_{i = 1}^m p_i = 1$，且 $p_i \ge 0$）作为权值。定义学生 $i$ 的加权总分为 $\sum_{j = 1}^m a_{i, j} \times p_j$，则按照加权总分降序排名，加权总分相等的则排名并列。 现在这 $m$ 个学科的老师都向你提出了要求，第 $k$ 个学科的老师想让你所设置的 $p$ 满足： - 以这个 $p$ 得到的排名结果中，不存在一对学生 $(x, y)$（$x \ne y$），使得 $x$ 排名更靠前（并列不算），但是 $a_{x, k} < a_{y, k}$； 因为你想要尽量自由的分配权值，所以你需要对于每个 $k$（$1 \le k \le m$），都**分别**求出： - $p_k$ 至少要为多少，才能保证**无论如何分配其他 $\boldsymbol{p_i}$ 的权值，都能满足**第 $k$ 个学科的老师的要求？请输出答案对 $998244353$ 取模的结果。

**本题单个测试点内包含多组数据。** 第一行一个整数 $T$ 表示数据组数。 接下来，对于每组数据，格式如下： 第一行两个整数，分别为 $n, m$。 第二行到第 $n + 1$ 行每行 $m$ 个整数，第 $i + 1$ 行第 $j$ 列的整数表示 $a_{i, j}$。

对于每组测试数据，输出 $m$ 行，每行一个非负整数，第 $i$ 行表示 $k = i$ 时，$p_k$ 的最小值对 $998244353$ 取模的结果。 即设答案化为最简分式后的形式为 $\frac{a} {b}$，其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx \equiv a \pmod{998244353}$ 且 $0 \le x < 998244353$。可以证明这样的整数 $x$ 是唯一的。

4
4 4
4 2 4 3
1 3 1 2
1 2 4 2
4 2 4 3
10 2
1 2
4 0
3 1
2 4
0 5
2 3
3 2
1 1
2 2
4 4
4 4
0 0 0 0
0 0 0 0
1 0 1 0
0 0 0 0
2 10
92603107 17358677 20869254 22085089 68529385 51524980 47064864 17692636 31121387 37022044
25517267 69562538 61254114 54886162 15087981 27505611 76082026 59892091 54661294 59475460

748683265
249561089
748683265
499122177
399297742
399297742
0
0
0
0
892513752
105730602
366911811
374997189
954012663
897963459
891479524
220357565
706471693
519276178

**【样例解释】** 对于第一组数据，询问的答案取模之前分别为 $\frac{1}{4}, \frac{3}{4}, \frac{1}{4}, \frac{1}{2}$。 对于第二组数据，询问的答案取模之前分别为 $\frac{4}{5}, \frac{4}{5}$。 对于第三组数据，询问的答案取模之前分别为 $0, 0, 0, 0$。 对于第一组数据的 $k = 2$ 的询问，假设 $p = [0.1, 0.75, 0.1, 0.05]$： - 第 $1$ 个学生的加权总分是 $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$； - 第 $2$ 个学生的加权总分是 $1 \times 0.1 + 3 \times 0.75 + 1 \times 0.1 + 2 \times 0.05 = 2.55$； - 第 $3$ 个学生的加权总分是 $1 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 2 \times 0.05 = 2.1$； - 第 $4$ 个学生的加权总分是 $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$； 则你令按加权总分降序排名的学生编号为 $[2, 4, 1, 3]$（当然也可以令其为 $[2, 1, 4, 3]$），且 $a_{2, 2} = 3, a_{4, 2} = 2, a_{1, 2} = 2, a_{3, 2} = 2$，不存在排名更靠后但是第 $2$ 个学科成绩更高的情况。 可以证明，在 $p_2 \ge 0.75$ 的情况下，无论其他 $p_i$ 如何分布，都可以满足要求；而 $p_2 < 0.75$ 的情况下，一定存在一种其他 $p_i$ 的分布使得无法满足要求。 **【数据范围】** **本题开启捆绑测试。** 设 $\sum nm$ 为单个测试点内所有的 $nm$ 之和。 对于 $100\%$ 的数据，$1 \le T \le 5 \times 10^4$，$ 2 \le n, m \le 10^5$，$ \sum nm \le 2 \times 10^5$，$ 0 \le a_{i, j} \leq 10^8$。 | 子任务编号 | $n$ | $m$ | $\sum nm$ | 特殊性质 | 分数 | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $\leq 10$ | $\leq 10$ | $\leq 100$ | 无 | $5$ | | $2$ | $\leq 100$ | $\leq 100$ | $\leq 10^4$ | 无 | $10$ | | $3$ | $\leq 5 \times 10^3$ | $\leq 5 \times 10^3$ | $\leq 10^4$ | 无 | $15$ | | $4$ | $\leq 100$ | $\le 10^5$ | $\le 2 \times 10^5$ | 无 | $20$ | | $5$ | $\le 10^5$ | $\leq 100$ | $\le 2 \times 10^5$ | 无 | $10$ | | $6$ | $\le 10^5$ | $\le 10^5$ | $\le 2 \times 10^5$ | $a_{i, j} \in \{0, 1\}$ | $20$ | | $7$ | $\le 10^5$ | $\le 10^5$ | $\le 2 \times 10^5$ | 无 | $20$ |