Public Judge

pjudge

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21731. 【CTS Round #1 Day 2】知识

统计

在板刷了 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$