题目背景

醒餞の鳥 (feat. Feryquitous) - Risa Yuzuki / 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$。