在板刷了 Yuhao Du Contest 7 后,你非常喜欢 Knowledge-Oriented Problem 一题。你认为这道题目很好地展现了你所拥有的知识,因此你打算在 CTS 的模拟赛中解决这样一道问题。
给定一个大小为 $M \times M$ 的矩阵 $A$ 与大小为 $N \times N$ 的矩阵 $B$。我们通过以下方式生成一张有向图 $G$:
- $G$ 中包含 $M \times N$ 个点,其中每个点可以用 $(i, j)$ 来表示($1 \le i \le M, 1 \le j \le N$)。
- 对于每个 $1 \le i,k \le M, 1 \le j \le N$,我们添加一条从 $(i, j)$ 连接到 $(k, j)$ 的有向边,权值为 $A_{i, k}$。
- 对于每个 $1 \le i \le M, 1 \le j,l \le N$,我们添加一条从 $(i, j)$ 连接到 $(i, l)$ 的有向边,权值为 $B_{j, l}$。
显然,最终我们将构造出一张大小为 $M \times N$ 的有向图。对于这张图的一棵外向树,我们定义它的权值为其所有边的边权之积。
现在,你想要知道,对于所有点 $(i, j)$($1 \le i \le M, 1 \le j \le N$),以 $(i, j)$ 为根的外向树的权值之和,取模 $998\,244\,353$。
输入格式
输入的第一行包含两个整数 $M, N$。
接下来 $M$ 行,包含 $M$ 个整数,其中第 $i$ 行的第 $k$ 个整数描述了元素 $A_{i, k}$。
接下来 $N$ 行,包含 $N$ 个整数,其中第 $j$ 行的第 $l$ 个整数描述了元素 $B_{j, l}$。
输出格式
输出 $M$ 行,每行 $N$ 个整数,第 $i$ 行的第 $j$ 个整数表示对于点 $(i, j)$ 的答案。
样例数据
样例输入
3 4
1 8 5
3 7 4
1 2 5
1 2 3 4
5 6 7 8
2 2 3 4
5 6 7 8
样例输出
225299668 249787015 956305250 832020912
12131995 203995081 507614573 801492956
360477413 73086353 551807495 381472353
子任务
对于所有数据,$1 \le M,N \le 500$,$0 \le A_{i, k}, B_{j, l} < 998\,244\,353$。
子任务 | $M,N \le$ | 特殊性质 | 分值 |
---|---|---|---|
$1$ | $10$ | $A,B$ 在范围内随机生成 | $5$ |
$2$ | $500$ | $A_{i,k}=B_{j,l} = 1$ | $6$ |
$3$ | $60$ | $A,B$ 在范围内随机生成 | $34$ |
$4$ | $150$ | $25$ | |
$5$ | $500$ | 无 | $30$ |