Background

Original link: https://oier.team/problems/S3D。

Problem Description

There are $n$ students (numbered $1 \sim n$) taking an exam with $m$ subjects (numbered $1 \sim m$). You are given that student $i$'s score in subject $j$ is $a_{i, j}$。

Now you want to rank these students. Since it is hard to compare the ability of two students whose scores do not form a partial order, you plan to set $m$ real numbers $p_{1 \sim m}$ (required to satisfy $\sum_{i = 1}^m p_i = 1$ and $p_i \ge 0$) as weights. Define student $i$'s weighted total score as $\sum_{j = 1}^m a_{i, j} \times p_j$. Then students are ranked in descending order of weighted total score, and students with equal weighted total score share the same rank。

Now all $m$ subject teachers have made requests to you. The teacher of subject $k$ wants your chosen $p$ to satisfy:

• In the ranking result obtained by this $p$, there does not exist a pair of students $(x, y)$ ($x \ne y$) such that $x$ ranks higher (ties do not count), but $a_{x, k} < a_{y, k}$。

Because you want to distribute the weights as freely as possible, for each $k$ ($1 \le k \le m$), you need to compute separately:

• What is the minimum value of $p_k$ such that no matter how the other $\boldsymbol{p_i}$ are distributed, the teacher of subject $k$'s requirement is always satisfied? Output the result modulo $998244353$。

Input Format

This problem contains multiple test cases within a single input file.

The first line contains an integer $T$ denoting the number of test cases。

For each test case, the format is:

The first line contains two integers $n, m$。

Lines $2$ to $n + 1$ each contain $m$ integers. The integer in row $i + 1$, column $j$ denotes $a_{i, j}$。

Output Format

For each test case, output $m$ lines, each containing a non-negative integer. The $i$-th line represents the result when $k = i$, i.e., the minimum value of $p_k$ modulo $998244353$。

That is, suppose the answer in lowest terms is $\frac{a}{b}$, where $a$ and $b$ are coprime. Output an integer $x$ such that $bx \equiv a \pmod{998244353}$ and $0 \le x < 998244353$。It can be proven that such an integer $x$ is unique。

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

Hint

[Sample Explanation]

For the first test case, the answers before taking modulo are $\frac{1}{4}, \frac{3}{4}, \frac{1}{4}, \frac{1}{2}$ respectively。

For the second test case, the answers before taking modulo are $\frac{4}{5}, \frac{4}{5}$ respectively。

For the third test case, the answers before taking modulo are $0, 0, 0, 0$ respectively。

For the query with $k = 2$ in the first test case, suppose $p = [0.1, 0.75, 0.1, 0.05]$:

• Student $1$'s weighted total score is $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$；
• Student $2$'s weighted total score is $1 \times 0.1 + 3 \times 0.75 + 1 \times 0.1 + 2 \times 0.05 = 2.55$；
• Student $3$'s weighted total score is $1 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 2 \times 0.05 = 2.1$；
• Student $4$'s weighted total score is $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$；

Then you rank the students (by descending weighted total score) as $[2, 4, 1, 3]$ (of course it can also be $[2, 1, 4, 3]$). Also, $a_{2, 2} = 3, a_{4, 2} = 2, a_{1, 2} = 2, a_{3, 2} = 2$, and there is no case where a lower-ranked student has a higher score in subject $2$。

It can be proven that when $p_2 \ge 0.75$, no matter how the other $p_i$ are distributed, the requirement can be satisfied; while when $p_2 < 0.75$, there must exist a distribution of the other $p_i$ that makes the requirement impossible to satisfy。

[Constraints]

This problem uses bundled tests.

Let $\sum nm$ be the sum of all $nm$ over all test cases within a single input file。

For $100\%$ of the testdata, $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$。

Translated by ChatGPT 5